क्रमपरिवर्तन पर पुनरावृति

लंबाई n का क्रमचय संख्या 1, 2, ..., n की पुनरावृत्ति के बिना एक क्रमबद्ध संग्रह है। उदाहरण के लिए, [3, 1, 2] और [5, 4, 3, 2, 1] क्रमपरिवर्तन हैं, लेकिन [1, 2, 1, 3] और [1, 2, 4] नहीं हैं।

यदि कार्य को इस तथ्य तक सीमित कर दिया जाता है कि लंबाई n के सभी क्रमपरिवर्तनों पर पुनरावृति करना आवश्यक है, तो आप C ++ में एक सुविधाजनक तंत्र का उपयोग कर सकते हैं, जिसे "next_permutation" कहा जाता है।

आप इसके बारे में documentation में अधिक पढ़ सकते हैं, लेकिन मुद्दा यह है कि यह फ़ंक्शन पारित सरणी को बदलता है लेक्सिकोग्राफिक क्रम में बाद के क्रमपरिवर्तन के लिए (जो आम तौर पर स्पष्ट और उसका नाम है)।

next_permutation का उपयोग करने के लिए, आपको एल्गोरिथम लाइब्रेरी शामिल करने की आवश्यकता है (यानी प्रोग्राम की शुरुआत में #include <algorithm> लिखें)

उदाहरण: वेक्टर गिरफ्तार; आगमन = {1, 2, 3}; // सरणी है [1, 2, 3] अगला_क्रमपरिवर्तन (arr.begin (), arr.end ()); // पूरे सरणी को फ़ंक्शन में पास करें // सरणी अब [1, 3, 2] है आगमन = {2, 3, 1}; // सरणी [2, 3, 1] है अगला_क्रमपरिवर्तन (arr.begin (), arr.end ()); // पूरे सरणी को फ़ंक्शन में पास करें // सरणी अब [3, 1, 2] है अगला_क्रमपरिवर्तन (arr.begin () + 1, arr.begin () + 3); // किसी फ़ंक्शन को सरणी के एक भाग पर लागू करना संभव है, लेकिन व्यवहार में इसकी शायद ही कभी आवश्यकता होती है // सरणी अब [3, 2, 1] है
इस स्थिति में, फ़ंक्शन का एक बूलियन रिटर्न मान होता है जो कि अगला क्रमचय उत्पन्न होने पर सत्य होता है और यदि अगला क्रमपरिवर्तन नहीं होता है तो असत्य होता है (ऐसा मामला जब लेक्सिकोग्राफ़िक क्रम में अधिकतम क्रमचय फ़ंक्शन को पास किया जाता है)।
यह लूप में फ़ंक्शन का उपयोग करना संभव बनाता है, जो हमें एक ही बार में सभी क्रमपरिवर्तनों पर पुनरावृति करने की अनुमति देगा। 0-अनुक्रमण के कारण, व्यवहार में अक्सर 0 से n-1 तक की संख्याओं के क्रमचय के साथ काम करना अधिक सुविधाजनक होता है, हालांकि एक क्रमचय में औपचारिक रूप से 1 से n तक की संख्याएँ होती हैं। लेकिन सौभाग्य से, इससे कोड में अतिरिक्त ओवरले नहीं होते हैं, क्योंकि अगला_परमुटेशन फ़ंक्शन 0-अनुक्रमित क्रमपरिवर्तन (और यहां तक ​​कि सरणी में डुप्लिकेट तत्वों के लिए भी अनुकूलित किया गया है, लेकिन आप अपने दम पर अधिक जानकारी प्राप्त कर सकते हैं)।

सामान्य तौर पर, सभी क्रमपरिवर्तनों पर पुनरावृति के लिए कोड इस तरह दिखता है:   इंटन; // क्रमपरिवर्तन आकार वेक्टर पर्म (एन); // पर्म "क्रमपरिवर्तन" के लिए छोटा है, अर्थात। "क्रमपरिवर्तन" के लिए (int i = 0; i < n; i++) पर्म [i] = मैं; // आरंभिक क्रमपरिवर्तन 0, 1, ..., n - 1 प्रारंभ करें करना { // लूप के अंदर हम वर्तमान क्रमचय को संसाधित करते हैं } जबकि (next_permutation(perm.begin(), perm.end())); // यदि कोई अगला क्रमचय नहीं है, तो लूप को समाप्त करें

यह कोड O(n! * f(n)) में चलता है, जहाँ f(n) वह समय है जो आपको एक विशेष क्रमचय को संसाधित करने में लगता है।