अनुक्रम

Question

आदेश देने के लिए न्यूनतम संख्या में स्वैप की गणना करें, पहले मैंने किसी भी संख्या के साथ एक पूर्णांक क्रम को क्रमबद्ध करने पर काम किया था (सामान्यता के नुकसान के बिना, आइए मान लें कि अनुक्रम 1,2,...,n का क्रमपरिवर्तन है) अपने प्राकृतिक बढ़ते क्रम (यानी 1,2,...,n) । मैं सोचता हूं कि कैसे तत्वों को स्वैप करना है (तत्वों की स्थिति के बावजूद, दूसरे शब्दों में, स्वैप किसी भी दो तत्वों के लिए मान्य है) न्यूनतम संख्या में स्वैप के साथ। मुझे लगता है कि निम्नलिखित एक व्यवहार्य एल्गोरिदम है:

बाधा के साथ दो तत्वों को स्वैप करें कि इनमें से एक या दोनों को सही स्थिति में बदल दिया जाना चाहिए। जब तक कि प्रत्येक तत्व को अपनी सही स्थिति में नहीं रखा जाता है।

लेकिन मुझे नहीं पता कि गणितीय रूप से साबित करने के लिए कि उपर्युक्त एल्गोरिदम इष्टतम समाधान का कारण बन सकता है या नहीं। कोई भी मदद कर सकता है?

बहुत बहुत धन्यवाद।

Answer 1

मैं इसे ग्राफ सिद्धांत के साथ साबित करने में सक्षम था। शायद उस टैग को जोड़ना चाहें :)

n शिखर के साथ एक ग्राफ बनाएं। यदि i स्थिति में तत्व सही क्रम में j स्थिति में होना चाहिए तो नोड n_i से n_j से किनारे बनाएं। अब आपके पास एक ग्राफ होगा जिसमें कई गैर-अंतरण चक्र शामिल होंगे। मैं तर्क है कि ग्राफ के आदेश करने के लिए आवश्यक स्वैप की न्यूनतम संख्या सही ढंग से

M = sum (c in cycles) size(c) - 1 

खुद इस बात का समझाने के लिए ... अगर दो आइटम एक चक्र में हैं, एक स्वैप सिर्फ उनकी देखभाल कर सकते हैं कुछ समय दें है। यदि तीन आइटम एक चक्र में हैं, तो आप एक जोड़ी को सही स्थान पर रखने के लिए एक दो-चक्र बना सकते हैं, और दो चक्र के अवशेष इत्यादि। यदि n आइटम एक चक्र में हैं, तो आपको n-1 स्वैप की आवश्यकता है। (यह हमेशा सत्य है यदि आप तत्काल पड़ोसियों के साथ स्वैप नहीं करते हैं।)

यह देखते हुए कि अब आप देख सकते हैं कि आपका एल्गोरिदम इष्टतम क्यों है। यदि आप स्वैप करते हैं और कम से कम एक आइटम सही स्थिति में होता है, तो यह हमेशा M के मान को 1 से कम कर देगा। n की किसी भी चक्र के लिए, किसी तत्व को सही स्थान पर स्वैप करने पर विचार करें, जो उसके पड़ोसी द्वारा कब्जा कर लिया गया है। अब आपके पास सही ढंग से आदेश दिया गया तत्व है, और लंबाई का चक्र n-1 है।

चूंकि M स्वैप की न्यूनतम संख्या है, और आपका एल्गोरिदम हमेशा प्रत्येक स्वैप के लिए M 1 को कम करता है, यह इष्टतम होना चाहिए।

Answer 2

आपके संदर्भ के लिए, यहां एक एल्गोरिदम है जिसे मैंने लिखा है, सरणी को सॉर्ट करने के लिए आवश्यक न्यूनतम स्वैप उत्पन्न करने के लिए। यह @Andrew Mao द्वारा वर्णित चक्रों को पाता है।

/** 
* Finds the minimum number of swaps to sort given array in increasing order. 
* @param ar array of <strong>non-negative distinct</strong> integers. 
*   input array will be overwritten during the call! 
* @return min no of swaps 
*/ 
public int findMinSwapsToSort(int[] ar) { 
    int n = ar.length; 
    Map<Integer, Integer> m = new HashMap<>(); 
    for (int i = 0; i < n; i++) { 
     m.put(ar[i], i); 
    } 
    Arrays.sort(ar); 
    for (int i = 0; i < n; i++) { 
     ar[i] = m.get(ar[i]); 
    } 
    m = null; 
    int swaps = 0; 
    for (int i = 0; i < n; i++) { 
     int val = ar[i]; 
     if (val < 0) continue; 
     while (val != i) { 
      int new_val = ar[val]; 
      ar[val] = -1; 
      val = new_val; 
      swaps++; 
     } 
     ar[i] = -1; 
    } 
    return swaps; 
} 

Answer 3

@bekce द्वारा अच्छी तरह से किया गया समाधान। सी # का उपयोग कर रहे हैं, तो संशोधित सरणी ar की स्थापना के प्रारंभिक कोड संक्षेप व्यक्त किया जा सकता है:

var origIndexes = Enumerable.Range(0, n).ToArray(); 
Array.Sort(ar, origIndexes); 

तो कोड के बाकी हिस्सों में origIndexes बजाय ar का उपयोग करें।

Answer 4

यह है कि स्वैप की न्यूनतम संख्या पाता (1,2,3,4,5,.......n-2,n-1,n)

#include<bits/stdc++.h> 
using namespace std; 


int main() 
{ 
    int n,i,j,k,num = 0; 
    cin >> n; 
    int arr[n+1]; 
    for(i = 1;i <= n;++i)cin >> arr[i]; 
    for(i = 1;i <= n;++i) 
    { 
     if(i != arr[i])// condition to check if an element is in a cycle r nt 
     { 
      j = arr[i]; 
      arr[i] = 0; 
      while(j != 0)// Here i am traversing a cycle as mentioned in 
      {    // first answer 
       k = arr[j]; 
       arr[j] = j; 
       j = k; 
       num++;// reducing cycle by one node each time 
      } 
      num--; 
     } 
    } 
    for(i = 1;i <= n;++i)cout << arr[i] << " ";cout << endl; 
    cout << num << endl; 
    return 0; 
}