क्रमपरिवर्तन में स्वैप की संख्या

Question

क्या कोई क्रमिक एल्गोरिदम (बड़े ओ नोटेशन के मामले में कुशल है) एक क्रमपरिवर्तन पी को पहचान क्रमपरिवर्तन में परिवर्तित करने के लिए स्वैप की संख्या खोजने के लिए? स्वैप को आसन्न तत्वों पर, लेकिन किसी भी तत्व पर होने की आवश्यकता नहीं है।

उदाहरण के लिए

तो:

I = {0, 1, 2, 3, 4, 5}, number of swaps is 0 
P = {0, 1, 5, 3, 4, 2}, number of swaps is 1 (2 and 5) 
P = {4, 1, 3, 5, 0, 2}, number of swaps is 3 (2 with 5, 3 with 5, 4 with 0) 

एक विचार इस तरह एक एल्गोरिथ्म लिखना है:

int count = 0; 
for(int i = 0; i < n; ++ i) { 
    for(; P[i] != i; ++ count) { // could be permuted multiple times 
     std::swap(P[P[i]], P[i]); 
     // look where the number at hand should be 
    } 
} 

लेकिन यह बहुत स्पष्ट है मेरे लिए है कि क्या है कि वास्तव में समाप्त करने के लिए गारंटी है या नहीं है कि क्या यह स्वैप की सही संख्या पाता है। यह उपरोक्त उदाहरणों पर काम करता है। मैंने 5 और 12 नंबरों पर सभी क्रमपरिवर्तन उत्पन्न करने की कोशिश की और यह हमेशा उन पर समाप्त हो जाता है।

यह समस्या संख्यात्मक रैखिक बीजगणित में उत्पन्न होती है। कुछ मैट्रिक्स अपघटन पिवोटिंग का उपयोग करते हैं, जो छोटी संख्याओं से विभाजन से बचने और संख्यात्मक स्थिरता में सुधार के लिए प्रभावी रूप से अगली पंक्ति के लिए अधिकतम मूल्य के साथ पंक्ति को स्वैप कर देता है। कुछ अपघटन, जैसे कि LU decomposition को बाद में मैट्रिक्स निर्धारक की गणना करने के लिए उपयोग किया जा सकता है, लेकिन विघटन की निर्धारक का संकेत मूल मैट्रिक्स के विपरीत है, यदि क्रमपरिवर्तन की संख्या विषम है।

EDIT: मैं मानता हूं कि यह प्रश्न Counting the adjacent swaps required to convert one permutation into another जैसा है। लेकिन मैं तर्क दूंगा कि यह सवाल अधिक मौलिक है। ओ (एन) में क्रम क्रमपरिवर्तन को परिवर्तित करके, ओ (एन) में क्रमपरिवर्तन लिखकर और फिर वहां से स्वैप की संख्या को पहचानने के लिए एक दूसरे से क्रमपरिवर्तन परिवर्तित करना इस समस्या में परिवर्तित किया जा सकता है। स्पष्ट रूप से पहचान का प्रतिनिधित्व करके इस प्रश्न को हल करना क्योंकि एक और क्रमपरिवर्तन उप-स्थानिक लगता है। इसके अलावा, दूसरा प्रश्न था, कल तक, चार उत्तरों जहां केवल एक ही (द्वारा | \/| विज्ञापन) प्रतीत होता था, लेकिन विधि का विवरण अस्पष्ट लग रहा था। अब उपयोगकर्ता लिज़ुसेक ने मेरे प्रश्न का उत्तर दिया। मैं इस सवाल को डुप्लिकेट के रूप में बंद करने से सहमत नहीं हूं।

EDIT2: प्रस्तावित एल्गोरिथ्म वास्तव में नहीं बल्कि सर्वोत्तम होने की, के रूप में उपयोगकर्ता rcgldr द्वारा एक टिप्पणी में कहा, Counting the adjacent swaps required to convert one permutation into another करने के लिए अपने जवाब देखने लगता है।

Answer 1

मेरा मानना ​​है कि cycle decomposition के संदर्भ में क्रमपरिवर्तन के बारे में सोचने की कुंजी है।

यह विघटन चक्रों के उत्पाद के रूप में कोई क्रमपरिवर्तन व्यक्त करता है।

मुख्य तथ्य हैं:

1. दो शिथिल चक्रों में गमागमन तत्वों एक लंबे समय तक चक्र का उत्पादन
2. एक ही चक्र में तत्वों गमागमन एक कम चक्र
3. जरूरत क्रमपरिवर्तन की संख्या nc जहाँ c है पैदा करता है अपघटन में चक्रों की संख्या

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

यदि वांछित है, तो आप चक्र अपघटन की गणना करके ओ (एन) में यह भी कर सकते हैं और पाए गए चक्रों की संख्या को कम कर सकते हैं।

चक्र अपघटन की गणना करना पहले नोड से शुरू करके और क्रमपरिवर्तन के बाद फिर से शुरू होने तक क्रमपरिवर्तन का पालन करके किया जा सकता है।सभी विज़िट किए गए नोड्स को चिह्नित करें, फिर अगले अनविजिटेड नोड पर फिर से शुरू करें।

Answer 2

मेरा मानना ​​है कि निम्नलिखित सत्य हैं:

1. हैं x[n - 1] == n - 1, तो S(x) == S(x[0],...,x[n-2]) (यानी, काट:

   तो S(x[0], ..., x[n-1]){0, 1, ..., n - 1} को x बदलने की जरूरत स्वैप की न्यूनतम संख्या है, तो है अंतिम तत्व)

2. यदि x[-1] != n - 1, तो S(x) == S(x[0], ..., x[n-1], ..., x[i], ... x[n-2]) + 1, जहां x[i] == n - 1।
3. S({}) = 0।

यह कंप्यूटिंग S(x) कि O(n) समय में चलाता है के लिए एक सरल एल्गोरिथ्म पता चलता है:

int num_swaps(int[] x, int n) { 
    if (n == 0) { 
    return 0; 
    } else if (x[n - 1] == n - 1) { 
    return num_swaps(x, n - 1); 
    } else { 
    int* i = std::find(x, x + n, n - 1); 
    std::swap(*i, x[n - 1]) 
    return num_swaps(x, n - 1) + 1; 
    } 
}