के साथ क्रमपरिवर्तन को सॉर्ट करना मुझे {1, 2, 3, ..., N} तत्वों का क्रमपरिवर्तन दिया गया है और मुझे इसे स्वैप ऑपरेशन का उपयोग करके सॉर्ट करना होगा। एक ऑपरेशन जो तत्व x को स्वैप करता है, y की लागत न्यूनतम (x, y) है।न्यूनतम लागत
मुझे क्रमपरिवर्तन क्रमबद्ध करने की न्यूनतम लागत जानने की आवश्यकता है। मैंने N से 1 पर जा रहे लालची के बारे में सोचा और एक स्वैप ऑपरेशन का उपयोग करके प्रत्येक तत्व को अपनी स्थिति में डाल दिया, लेकिन यह एक अच्छा विचार नहीं है।
आप क्रमचय संख्या 1, 2, ... की है, तो एन, तो अनुसार क्रमबद्ध संग्रह ठीक 1, 2, ..., एन हो जाएगा। तो आप जटिलता ओ (0) के साथ जवाब जानते हैं (यानी आपको बिल्कुल एल्गोरिदम की आवश्यकता नहीं है)।
आप वास्तव में दोहराया अदला-बदली से सीमा क्रमबद्ध करना चाहते हैं, तो आप बार-बार कर सकते हैं "अग्रिम और चक्र": पहले से ही हल कर सीमा पर अग्रिम (जहां a[i] == i), और फिर आप जब तक a[a[i]] साथ a[i] स्वैप चक्र को पूरा । जब तक आप अंत तक नहीं पहुंच जाते तब तक दोहराएं। इसकी आवश्यकता है एन − 1 स्वैप, और यह मूल रूप से क्रमपरिवर्तन के चक्र अपघटन करता है।
हम्म। एक दिलचस्प सवाल है। मेरे दिमाग में आने वाला एक त्वरित एल्गोरिदम तत्वों के रूप में तत्वों का उपयोग करना है। हम पहले एक तत्व की अनुक्रमणिका पाते हैं जिसमें 1 मान के रूप में होता है, और उस संख्या के तत्व के साथ इसे स्वैप करता है। आखिरकार यह 1 स्थिति के साथ पहली स्थिति में दिखाई देगा, इसका मतलब है कि आपको कुछ तत्वों के साथ 1 को स्वैप करना होगा जो अभी तक स्थिति में नहीं है, और जारी रखें। यह 2 * एन -2 पर सबसे ऊपर है, और क्रमपरिवर्तन के लिए एन -1 पर निचली सीमा है (2,3, ..., एन, 1), लेकिन सटीक लागत अलग-अलग होगी।
ठीक है, ऊपर दिए गए एल्गोरिदम और उदाहरणों के बाद, मुझे लगता है कि सबसे इष्टतम होगा जब तक कि यह पहले स्थान पर न हो, तब तक किसी भी चीज़ के साथ 1 का आदान-प्रदान करने का पालन करना होगा, फिर दूसरे स्थान के साथ 2 का आदान-प्रदान करें, यदि यह पहले से मौजूद नहीं है, तो 1 को स्वैप करना जारी रखें सॉर्ट किए जाने तक, अभी तक कुछ भी नहीं है।
set sorted=false
while (!sorted) {
if (element 1 is in place) {
if (element 2 is in place) {
find any element NOT in place
if (no element found) sorted=true
else {
swap 1 with element found
cost++
}
} else {
swap 2 with element at second place
cost+=2
}
} else {
find element with number equals to position of element 1
swap 1 with element found
cost++
}
}
वास्तविक प्रश्न टिप्पणियों में उदाहरण [4,3,2,1] को देखते हुए, 3 की इष्टतम लागत के साथ, केवल 1 के साथ स्वैप करके अटूट, सही एल्गोरिदम को और अधिक जटिल होना चाहिए। – hyde
ठीक है, आपके एल्गोरिदम के साथ एक counterexample [2,3,1] आप 3 के साथ समाप्त होता है, मेरा, 2 - एक्सचेंज 1 के साथ 3, फिर 1 के साथ 2. – Vesper
सच है, मुझे संदेह है कि पूरे एल्गोरिहम को थोड़ा सा होना चाहिए अधिक जटिल, हालांकि मुझे लगता है कि मैं अपने संस्करण को थोड़ा सा बदल दूंगा ताकि इसे [4,3,2,1] और [2,3,1] दोनों को कवर किया जा सके। – hyde
की 1.
लागत शून्य है बाल्टी के आकार के साथ एक बाल्टी प्रकार का उपयोग करें, क्योंकि कोई स्वैप होते हैं। अब बाल्टी सरणी के माध्यम से एक पास करें, और प्रत्येक मान को मूल सरणी में इसके संबंधित स्थिति में वापस स्वैप करें।
वह एन स्वैप है।
एन की राशि एन (एन + 1)/2 है जो आपको एक निश्चित निश्चित लागत दे रही है।
एक अलग व्याख्या यह है कि आप बस बाल्टी सरणी से वापस मूल सरणी में स्टोर करते हैं। यह कोई स्वैप नहीं है, इसलिए लागत शून्य है, जो एक उचित न्यूनतम है।
इस इष्टतम होगा:
Find element 2
If it is not at correct place already
Find element at position 2
If swapping that with 2 puts both to right place
Swap them
Cost = Cost + min(2, other swapped element)
repeat
Find element 1
If element 1 is at position 1
Find first element that is in wrong place
If no element found
set sorted true
else
Swap found element with element 1
Cost = Cost + 1
else
Find element that should go to the position where 1 is
Swap found element with element 1
Cost = Cost + 1
until sorted is true
शायद ऑप्टिकल गणितीय रूप से, लेकिन गोटो ... – WLPhoenix
इस एल्गोरिदम के बारे में मेरा खुद का आरक्षण है: 1. क्या पहले 2 से निपटना ठीक है, या लूप के बीच में कहीं से निपटना बेहतर होगा, कुछ के साथ शर्त? 2. क्या इससे कोई फर्क नहीं पड़ता कि गलत पर कौन सा तत्व 1 से swappping के लिए चुना गया है, जब 1 अपनी जगह पर समाप्त होता है? – hyde
@WLPhoenix ठीक जुर्माना, गेटोस की जगह, ब्रेक का उपयोग भी नहीं किया। खुश? ;) – hyde
चाहता है तो तुच्छ हैं, तो स्वैप की न्यूनतम संख्या के चक्र की संख्या से निर्धारित किया जाएगा। यह Cuckoo Hashing के समान सिद्धांत का पालन करेगा। आप क्रमपरिवर्तन में पहला मान लेते हैं, और मूल अनुक्रमणिका में मान के सूचकांक पर मान को देखते हैं। यदि वे मेल खाते हैं, तो एक ही ऑपरेशन के लिए स्वैप करें।
[ 2 1]: वैल्यू 3 इंडेक्स पर है, इसलिए इंडेक्स 3 पर मान देखें।
[3 2 ]: मान 1 सूचकांक 3 पर है, इसलिए दो सूचकांक चक्र मौजूद हैं। इन मूल्यों को स्वैप करें।
यदि नहीं, तो पहले इंडेक्स को स्टैक पर दबाएं और दूसरी अनुक्रमणिका के मान के लिए इंडेक्स की तलाश करें। आखिर में एक चक्र होगा। उस बिंदु पर, ढेर से मूल्यों को पॉप करके स्वैप करना प्रारंभ करें। यह एन -1 के बराबर कई स्वैप लेगा, जहां एन चक्र की लंबाई है।
[ 1 2]: मूल्य 3 सूचकांक एक पर है, इसलिए सूचकांक में मूल्य को देखने 3.
[3 1 ]: मान 2 सूचकांक 3 में है, इसलिए 3 करने के लिए जोड़ ढेर और इंडेक्स की तलाश 2. चक्र के शुरुआती मूल्य के रूप में 3 स्टोर करें।
[3 2]: मान 1 सूचकांक 2 में है, इसलिए ढेर करने के लिए 2 जोड़ सकते हैं और सूचकांक की तलाश 1.
[ 1 2]: मूल्य 3 चक्र की शुरुआत है, इसलिए स्वैप स्टैक से पॉप 2 और स्वैप मान 1 और 2.
[1 3 2]: स्टैक से पॉप 3 और 2 और 3 स्वैप करें, जिसके परिणामस्वरूप 2 स्वैप के साथ सॉर्ट की गई सूची होती है।
[1 2 3]
, स्वैप की अधिकतम संख्या एन -1, जहां N मानों की कुल संख्या है किया जाएगा। यह तब होता है जब एन लंबाई चक्र होता है।
संपादित करें: यह एल्गोरिदम न्यूनतम स्वैप देता है, लेकिन न्यूनतम (x, y) फ़ंक्शन का उपयोग करके न्यूनतम मूल्य आवश्यक नहीं है। मैंने गणित नहीं किया है, लेकिन मुझे विश्वास है कि एकमात्र समय जब स्वैप (एक्स, वाई) = {स्वैप (1, एक्स), स्वैप (1, वाई), स्वैप (1, एक्स)} का उपयोग नहीं किया जाना चाहिए जब x {2,3} और n < 2 में x है; एक विशेष मामले के रूप में लिखने के लिए पर्याप्त आसान होना चाहिए। 2 और 3 को स्पष्ट रूप से जांचना और स्थानांतरित करना बेहतर हो सकता है, फिर दो संचालन में सॉर्टिंग प्राप्त करने के लिए टिप्पणियों में उल्लिखित एल्गोरिदम का पालन करें।
संपादित करें 2: बहुत यकीन है कि यह सभी मामलों को पकड़ लेगा।
while (unsorted) {
while (1 != index(1))
swap (1 , index (1))
if (index(2) == [email protected](2))
swap (2, [email protected](2))
else
swap (1 , highest value out of place)
}
यह मुझे किसी कारण से संपादित करने की अनुमति नहीं दे रहा है, लेकिन अगर यह भी शर्त हो कि 2 और मूल्य @ (2) स्थान के बाहर एकमात्र मूल्य हैं। – WLPhoenix
तो, क्या मुझे प्रश्न सही है: आप क्रमपरिवर्तन दे रहे हैं। इस दिए गए क्रमपरिवर्तन के लिए, आपको प्रति स्वैप के साथ उस स्वैप ऑपरेशन का उपयोग करके इसे क्रमबद्ध करने की न्यूनतम लागत की आवश्यकता है? – hyde
स्वैप लागत, एक्स और वाई तत्व अंतिम स्थिति या मान हैं, या वे वर्तमान में स्थिति तत्व हैं? – hyde
... असल में, क्या यह एक चाल सवाल है? यदि लागत न्यूनतम (एक्स, वाई) है, तो आप हमेशा 1 के साथ स्वैप करें ... सही स्थिति में तत्व प्राप्त करने के लिए दो स्वैप। – hyde