यादृच्छिक क्रम में पूर्णांकों की एक सरणी आप इसे क्रमबद्ध सरणी

Question

चक्रीय करने के लिए यदि एक सरणी यादृच्छिक क्रम में दिया जाता है परिवर्तित करने के लिए स्वैप की न्यूनतम संख्या खोजने के लिए दिया जाता है, आप चक्रीय में परिवर्तित करने के लिए आवश्यक स्वैप की न्यूनतम संख्या उत्पादन करने के लिए है सॉर्टेड सरणी

उदा। 3 4 5 2 1 दूसरा स्वैप 2 < हो जाएगा -> 1 परिणाम: 3 4 5 1 2 (> 4 परिणाम - दिया सरणी 3 5 4 2 1

तो पहले स्वैप 5 < हो जाएगा अंतिम)

उत्पादन: 2

मैं इस समस्या के पीछे तर्क प्राप्त करने में सक्षम नहीं हूँ।

कुछ और जोड़ने: आसन्न तत्वों और संख्याओं के बीच स्वैप ही संभव एन

Answer 1

को सीमा 1 के बीच हैं मुझे लगता है कि दृष्टिकोण यहाँ होना चाहिए - तरह सब एक सहायक सरणी में संख्या। फिर प्रत्येक चक्रीय बदलाव के लिए इस चक्रीय बदलाव करने के लिए मूल सरणी प्राप्त करने के लिए आवश्यक स्वैप की संख्या की गणना। उनमें से कम से कम चुनें।

सरणी ए को सरणी प्राप्त करने के लिए आवश्यक स्वैप की न्यूनतम संख्या को खोजने के लिए केवल इंटरचेंज किए गए मानों की संख्या गिनती है (यानी मान ए में मान बी के बाईं ओर है लेकिन सरणी बी के विपरीत है)। यह समस्या किसी दिए गए सरणी में व्युत्क्रम गिनती के बराबर है और संशोधित मर्ज O(n*log(n)) में तरह फिर से उपयोग हल किया जा सकता।

मेरे दृष्टिकोण की जटिलता O(n^2*log(n)) है (क्योंकि आप आकार की सरणी के सभी चक्रीय बदलावों के लिए विलय प्रकार करते हैं)।

मैं आपकी समस्या के लिए तेज़ समाधान के बारे में नहीं सोच सकता।

Answer 2

ठीक है, अगर यह सबसे अच्छा कलन विधि उपलब्ध है पता नहीं है, लेकिन मैं एक O (n^2) समाधान के बारे में सोच सकते हैं:

पहले, चक्रीय सरणी की संभावना पर ध्यान न दें। आइए एक सरल समस्या हल करें: सरणी को सॉर्ट करने के लिए न्यूनतम संख्या में स्वैप क्या है।

यहाँ सावधान रहें

, क्योंकि इस एल्गोरिदम छँटाई के बारे में नहीं है। एक comparation आधारित छंटाई एल्गोरिथ्म कम से कम O(n log n) की बुरी से बुरी हालत के लिए होगा। इस समस्या में, स्वैप की अधिकतम संख्या की जरूरत n है।

क्यों? क्योंकि यह अधिकतम permutation cycle size है जिसे आप प्राप्त कर सकते हैं। आपको आवश्यक स्वैप की न्यूनतम संख्या बिल्कुल क्रमपरिवर्तन चक्र आकार शून्य है। मेरा मतलब है आप जैसे किसी परिवर्तन चक्र के रूप में सरणी के किसी भी परिवर्तन, .:

3 2 1 4 5 प्रतिनिधित्व कर सकते हैं - आकार 1 के क्रमपरिवर्तन चक्र के लिए>(2)(4)(5)(1 3)

, आप किसी भी स्वैप जरूरत नहीं है। आकार 2 के क्रमपरिवर्तन चक्र के लिए, आपको बिल्कुल 1 स्वैप की आवश्यकता है। >(1 2 3 4 5)

इस सरणी की उपेक्षा कर पहले से ही चक्रीय-छाँटे गए है, इस सरणी tottaly गड़बड़ है -

2 3 4 5 1: यह रूप में मापता है। इसे सामान्य रूप से सॉर्ट करने के लिए, मुझे 4 स्वैप की आवश्यकता होगी, मूल रूप से 1 को इसकी सामान्य स्थिति में ले जाया जाएगा।

क्रमपरिवर्तन चक्रों की गणना करना बहुत आसान है, यह केवल उस संख्या का पालन करने का विषय है जहां सरणी को सॉर्ट किया गया था। A[0] पर पिछले उदाहरण

3 2 1 4 5

• शुरू होता है का उपयोग करना;
• क्योंकि A[0]==3, और 3 क्रमबद्ध सरणी में तीसरा तत्व होगा, तीसरी स्थिति के बाद;

• क्योंकि A[2]==1, और 1 होगा ..., 1 स्थिति के बाद होगा। जैसा कि हम पहले से ही थे, हमारे पास आकार 2 का चक्र है; अगले विज़िट नहीं किए गए स्थिति (1)

• A[1]==2 है यह सही स्थिति है, इसलिए हम कुछ भी करने की जरूरत नहीं है में कम से फिर से

• शुरू होता है, यहाँ हम आकार 1 का एक चक्र है।

• और बहुत आगे है ...

इस एल्गोरिथ्म हे (एन) है, लेकिन जैसा कि हम सरणी हर संभव स्थिति में शुरू होने वाले (क्योंकि यह परिपत्र है) के लिए ऐसा करने की जरूरत है, हम करेंगे इसे एन बार करें, इसलिए, संपूर्ण एल्गोरिदम ओ (एन^2) है।

अद्यतन; कुछ अजगर कोड मेरी एल्गोरिथ्म को दिखाने के लिए:

def offset_swaps(A, S, offset): 
    visited = [False]*len(A) 
    swaps = 0 

    for i in xrange(len(A)): 
     if visited[i]: continue 

     cycle, current = 0, i 
     while not visited[current]: 
      cycle += 1 
      visited[current] = True 
      current = (S[A[current]] + offset) % len(A) 

     swaps += cycle - 1 

    return swaps  

def number_of_swaps(A): 
    S = {x:i for i,x in enumerate(sorted(A))} 
    min_swaps = len(A) 
    for i in xrange(len(A)): 
     min_swaps = min(min_swaps, offset_swaps(A, S, i)) 
    return min_swaps 

print number_of_swaps((3, 5, 4, 2, 1)) 

Answer 3

मान लिया जाये:

1. एक का आवंटन:
   1. सरणी तत्वों पूर्णांकों 1 एन

   कदम के लिए कर रहे दूसरा (हिस्टोग्राम) सरणी लंबाई एच

2. प्रारंभिक सरणी ए के माध्यम से एक ही पास में, प्रत्येक इंडेक्स के लिए मैं एच बढ़ाता हूं [(ए [i] - i)% N]
3. एच के माध्यम से एक ही पास में, अधिकतम गणना
के साथ एच के तत्व आर की पहचान करें
4. साफ़ एच
5. आर द्वारा घूर्णन के तहत मूल सरणी में ऑर्बिट्स की संख्या की पहचान करें (एच के माध्यम से एच [i] = 0 तक आगे बढ़कर, फिर कक्षा के माध्यम से आगे बढ़कर जिसके लिए ए [i] एक है घूर्णन के तहत सदस्य आर) कक्षा के प्रत्येक सदस्य के लिए एच [i] = 1 सेट करना, और जब तक तत्व एच [एन -1] संसाधित नहीं किया जाता है तब तक दोहराया जाता है (जब आप जाते हैं कक्षाओं के नम्बर को गिनते हैं)। यह ओ (एन) भी है क्योंकि ए के प्रत्येक तत्व को एक बार देखा जाता है।
6. आवश्यक संख्या स्वैप = एन - कक्षाएं।

यह ओ (एन) है।

अपडेट: मैंने एकाधिक कक्षाओं के लिए खाते में एल्गोरिदम अपडेट किया है। प्रत्येक कक्षा को संसाधित करने में, अंतिम स्वैप केवल 1 के बजाय दो तत्व रखता है।

मुझे संदेह है कि ऑर्बिट्स की संख्या किसी भी घूर्णन के तहत परिवर्तनीय है, जो एल्गोरिदम को समझदारी से सरल बनाती है लेकिन इसकी जटिलता को प्रभावित नहीं करती है, जो ओ (एन) में बनी हुई है।

Answer 4

def number_of_swaps(A): 
    l=len(A) 
    if l < 2: 
     return 0 
    S1={x:i for i,x in enumerate(A)} 
    pos_of_0=S1[0] 
    pos_of_N=S1[l-1] 
    if pos_of_0 > 0: 
     if pos_of_N != (l-1): 
      if pos_of_N < pos_of_0: 
       n=(pos_of_0+(l-1)-pos_of_N-1) 
      else: 
        n=(pos_of_0+(l-1)-pos_of_N) 
     else: 
      n=(pos_of_0) 
    else : 
     n=(l-pos_of_N-1) 
    A.remove(0) 
    A.remove(l-1) 
    B=[x-1 for x in A ] 
    return n+number_of_swaps(B) 

def min_number_of_swaps(A): 
    B=sorted(A) 
    swaps=[] 
    for i in range(len(A)): 
     if i == 0: 
      C=B 
     else: 
      C=B[-i:]+B[0:len(A)-i] 

     S = {x:i for i,x in enumerate(C)} 
     D=[S[i] for i in A] 
     swaps.append(number_of_swaps(D)) 
    return min(swaps) 

प्रिंट min_number_of_swaps ([8,5,7,1,2,4,3,6])

से ऊपर कोड isrecursive दृष्टिकोण समस्या जटिलता हे हल करने के लिए (एन^3)

कोड को केवल न्यूनतम संख्या में स्वैप मुद्रित करने के लिए संपादित किया गया है।