क्रमचय: Difference between revisions

Line 166:

=== दोहराव के साथ क्रमपरिवर्तन ===

समुच्चय S के k तत्वों की क्रमबद्ध व्यवस्था, जहाँ पुनरावृत्ति की अनुमति है, k-टपल्स कहलाती हैं। उन्हें कभी-कभी पुनरावृत्ति के साथ क्रमपरिवर्तन के रूप में संदर्भित किया जाता है, ~~हालांकि~~ वे सामान्य रूप से क्रमपरिवर्तन नहीं होते हैं। उन्हें कुछ संदर्भों में अक्षर S पर शब्द भी कहा जाता है। यदि समुच्चय S में n अवयव हैं, तो S पर k-टपल्स की संख्या <math>n^k.</math> कोई तत्व k-टपल में कितनी बार प्रकट हो सकता है, इस पर कोई प्रतिबंध नहीं है, लेकिन यदि कोई तत्व कितनी बार दिखाई दे सकता है, इस पर प्रतिबंध लगाया जाता है, तो यह सूत्र अब मान्य नहीं है।

समुच्चय S के k तत्वों की क्रमबद्ध व्यवस्था, जहाँ पुनरावृत्ति की अनुमति है, k-टपल्स कहलाती हैं। उन्हें कभी-कभी पुनरावृत्ति के साथ क्रमपरिवर्तन के रूप में संदर्भित किया जाता है, चूंकि वे सामान्य रूप से क्रमपरिवर्तन नहीं होते हैं। उन्हें कुछ संदर्भों में अक्षर S पर शब्द भी कहा जाता है। यदि समुच्चय S में n अवयव हैं, तो S पर k-टपल्स की संख्या <math>n^k.</math> कोई तत्व k-टपल में कितनी बार प्रकट हो सकता है, इस पर कोई प्रतिबंध नहीं है, लेकिन यदि कोई तत्व कितनी बार दिखाई दे सकता है, इस पर प्रतिबंध लगाया जाता है, तो यह सूत्र अब मान्य नहीं है।

=== मल्टीसेट्स के क्रमपरिवर्तन ===

Line 214:

परिमित समुच्चय के प्रत्येक क्रमचय को स्थानान्तरण के गुणनफल के रूप में व्यक्त किया जा सकता है। [36] ~~हालांकि~~ एक दिए गए क्रमचय के लिए ऐसे कई व्यंजक मौजूद हो सकते हैं, या तो उन सभी में ट्रांसपोज़िशन की एक समान संख्या होती है या उन सभी में विषम संख्या में ट्रांसपोज़िशन होते हैं। इस प्रकार सभी क्रमचयों को इस संख्या के आधार पर [[सम या विषम के रूप में वर्गीकृत]] किया जा सकता है।

परिमित समुच्चय के प्रत्येक क्रमचय को स्थानान्तरण के गुणनफल के रूप में व्यक्त किया जा सकता है। [36] चूंकि एक दिए गए क्रमचय के लिए ऐसे कई व्यंजक मौजूद हो सकते हैं, या तो उन सभी में ट्रांसपोज़िशन की एक समान संख्या होती है या उन सभी में विषम संख्या में ट्रांसपोज़िशन होते हैं। इस प्रकार सभी क्रमचयों को इस संख्या के आधार पर [[सम या विषम के रूप में वर्गीकृत]] किया जा सकता है।

इस परिणाम को बढ़ाया जा सकता है ताकि प्रत्येक क्रमचय के लिए <math>\operatorname{sgn}\sigma</math> लिखा हुआ एक चिह्न निर्दिष्ट किया जा सके। <math>\operatorname{sgn}\sigma = +1</math> अगर <math>\sigma</math> सम है और <math>\operatorname{sgn}\sigma = -1</math> यदि <math>\sigma</math> विषम है। फिर दो क्रमपरिवर्तन के लिए <math>\sigma</math> तथा <math>\pi</math>

Line 239:

n के क्रमचय σ का आरोहण कोई भी स्थिति i < n है जहां निम्न मान वर्तमान मान से बड़ा है। अर्थात, यदि σ = σ1σ2...σn, तो i एक आरोहण है यदि σi < σi+1। उदाहरण के लिए, क्रमपरिवर्तन 3452167 में आरोही (स्थितियों पर) 1, 2, 5 और 6 हैं। इसी तरह, एक डिसेंट i < n के साथ σi > σi+1 की स्थिति है, इसलिए <math>1 \leq i<n</math> के साथ हर i या तो एक आरोही है या एक डिसेंट है σ। क्रमचय का एक आरोही क्रम क्रमचय का एक गैर-खाली बढ़ता हुआ सन्निकट क्रम है जिसे किसी भी छोर पर विस्तारित नहीं किया जा सकता है; यह लगातार चढ़ाई के अधिकतम अनुक्रम से मेल खाता है (उत्तरार्द्ध खाली हो सकता है: दो लगातार अवरोही के बीच अभी भी लंबाई 1 का आरोही रन है)। इसके विपरीत एक क्रमचय का एक बढ़ता क्रम आवश्यक रूप से सन्निहित नहीं है: यह कुछ स्थितियों पर मानों को छोड़ कर क्रमचय से प्राप्त तत्वों का बढ़ता क्रम है। उदाहरण के लिए, क्रमचय 2453167 में आरोही रन 245, 3, और 167 हैं, जबकि इसके बढ़ते क्रमांक 2367 हैं। यदि एक क्रमचय में k - 1 अवरोही है, तो यह k आरोही रन का संघ होना चाहिए।{{sfn|Bóna|2004|p=4f}}

k आरोही के साथ n के क्रमपरिवर्तन की संख्या है (परिभाषा के अनुसार) यूलेरियन संख्या <math>\textstyle\left\langle{n\atop k}\right\rangle</math> सही\rangle; यह k अवरोही के साथ n के क्रमचय की संख्या भी है। ~~हालांकि~~ कुछ लेखक ऑयलेरियन संख्या <math>\textstyle\left\langle{n\atop k}\right\rangle</math> को k के साथ क्रमपरिवर्तन की संख्या के रूप में परिभाषित करते हैं। आरोही रन, जो {{nowrap|''k'' − 1}} अवरोही के अनुरूप है।{{sfn|Bona|2012|pages=4–5}} क्रमचय σ1σ2...σn की अधिकता एक सूचकांक j है जैसे कि {{nowrap|''σ''''j'' > ''j''}}. यदि असमानता सख्त नहीं है (अर्थात, {{nowrap|''σ''''j'' ≥ ''j''}}), तो j को एक कमजोर अतिरेक कहा जाता है। k अधिकता वाले n-क्रमपरिवर्तन की संख्या k अवरोही के साथ n-क्रमपरिवर्तन की संख्या के साथ मेल खाती है।{{sfn|Bona|2012|page=25}}

k आरोही के साथ n के क्रमपरिवर्तन की संख्या है (परिभाषा के अनुसार) यूलेरियन संख्या <math>\textstyle\left\langle{n\atop k}\right\rangle</math> सही\rangle; यह k अवरोही के साथ n के क्रमचय की संख्या भी है। चूंकि कुछ लेखक ऑयलेरियन संख्या <math>\textstyle\left\langle{n\atop k}\right\rangle</math> को k के साथ क्रमपरिवर्तन की संख्या के रूप में परिभाषित करते हैं। आरोही रन, जो {{nowrap|''k'' − 1}} अवरोही के अनुरूप है।{{sfn|Bona|2012|pages=4–5}} क्रमचय σ1σ2...σn की अधिकता एक सूचकांक j है जैसे कि {{nowrap|''σ''''j'' > ''j''}}. यदि असमानता सख्त नहीं है (अर्थात, {{nowrap|''σ''''j'' ≥ ''j''}}), तो j को एक कमजोर अतिरेक कहा जाता है। k अधिकता वाले n-क्रमपरिवर्तन की संख्या k अवरोही के साथ n-क्रमपरिवर्तन की संख्या के साथ मेल खाती है।{{sfn|Bona|2012|page=25}}

=== फोटा का संक्रमण लेम्मा ===

Line 246:

चलो <math>f(p)=q</math> कोष्ठक-मिटाने वाला परिवर्तन हो जो <math>q</math> को एक-पंक्ति नोटेशन में लौटाता है <math>p</math> विहित में चक्र अंकन। जैसा कि कहा गया है, <math>f</math> सभी कोष्ठकों को हटाकर संचालित होता है। व्युत्क्रम परिवर्तन का संचालन, {<math>f^{-1}(q)=p</math>, जो एक-पंक्ति संकेतन में <math>q</math> दिए जाने पर विहित चक्र संकेतन में <math>p</math> लौटाता है, यह थोड़ा कम सहज है। <math>q = q_1q_2\cdots q_n</math> का पहला चक्र p}p विहित चक्र संकेतन में <math>q_1</math> से शुरू होना चाहिए। जब तक बाद के तत्व <math>q_1</math> से छोटे हैं, हम <math>p</math> के समान चक्र में हैं। <math>p</math> का दूसरा चक्र सबसे छोटे इंडेक्स <math>j</math> से शुरू होता है, जैसे कि <math>q_j > q_1</math>। दूसरे शब्दों में, <math>q_j</math> अपने बायीं ओर की सभी चीज़ों से बड़ा है, इसलिए इसे बाएँ से दाएँ अधिकतम कहा जाता है। कैनोनिकल चक्र संकेतन में प्रत्येक चक्र बाएं से दाएं अधिकतम के साथ शुरू होता है।{{sfn|Bona|2012|pp=109–110}}

उदाहरण के लिए, क्रमचय में <math>q=312548976</math>, 5 पहला तत्व है जो प्रारंभिक तत्व 3 से बड़ा है, इसलिए <math>p</math> का पहला चक्र <math>(\,3\,1\,2\,)</math> होना चाहिए। फिर 8 अगला तत्व 5 से बड़ा है, तो दूसरा चक्र है <math>(\,5\,4\,)</math>। चूँकि 9, 8 से बड़ा है, <math>(\,8\,)</math> अपने आप में एक चक्र है। अंत में, 9 अपने दाहिनी ओर शेष सभी तत्वों से बड़ा है, इसलिए अंतिम चक्र है ~~{\displaystyle~~ (\,9\,7\,6~~\,)}{\displaystyle (\,9\,7\,6\,~~)}। इन 4 चक्रों को जोड़ने पर <math>p=(\,3\,1\,2\,)(\,5\,4\,)(\,8\,)(\,9\,7\,6\,)</math> विहित चक्र अंकन में।

उदाहरण के लिए, क्रमचय में <math>q=312548976</math>, 5 पहला तत्व है जो प्रारंभिक तत्व 3 से बड़ा है, इसलिए <math>p</math> का पहला चक्र <math>(\,3\,1\,2\,)</math> होना चाहिए। फिर 8 अगला तत्व 5 से बड़ा है, तो दूसरा चक्र है <math>(\,5\,4\,)</math>। चूँकि 9, 8 से बड़ा है, <math>(\,8\,)</math> अपने आप में एक चक्र है। अंत में, 9 अपने दाहिनी ओर शेष सभी तत्वों से बड़ा है, इसलिए अंतिम चक्र है (9,7,6)। इन 4 चक्रों को जोड़ने पर <math>p=(\,3\,1\,2\,)(\,5\,4\,)(\,8\,)(\,9\,7\,6\,)</math> विहित चक्र अंकन में।

निम्न तालिका <math>q</math> और <math>p</math> दोनों को <math>123</math> के छह क्रमपरिवर्तनों के लिए दिखाती है। प्रत्येक समानता का बोल्ड पक्ष अपने नामित संकेतन <math>q</math> के लिए एक-पंक्ति संकेतन और <math>p</math> के लिए विहित चक्र संकेतन) का उपयोग करके क्रमपरिवर्तन दिखाता है, जबकि गैर-बोल्ड पक्ष दूसरे में समान क्रमचय दिखाता है अंकन। तालिका के प्रत्येक स्तंभ के बोल्ड पक्ष की तुलना करने से फोटा के आक्षेप के संचालन को हटाने/पुनर्स्थापना करने वाले कोष्ठक को दर्शाता है, प्रत्येक स्तंभ के एक ही पक्ष की तुलना करते समय (उदाहरण के लिए, बायाँ पक्ष) दिखाता है कौन से क्रमपरिवर्तन खुद को बायजेक्शन (पहली 3 पंक्तियों) द्वारा मैप किए जाते हैं और कौन से नहीं हैं (अंतिम 3 पंक्तियाँ)।

Line 282:

}}</ref>]]क्रमपरिवर्तन σ का व्युत्क्रम पदों की एक जोड़ी (i, j) है जहां क्रमचय की प्रविष्टियां विपरीत क्रम में होती हैं: <math>\sigma_i > \sigma_j</math>{{sfn|Bóna|2004|p=43}} तो <math>i < j</math> दो आसन्न स्थितियों पर एक व्युत्क्रम है। उदाहरण के लिए, क्रमपरिवर्तन σ = 23154 में तीन व्युत्क्रम हैं: (1, 3), (2, 3), और (4, 5), प्रविष्टियों के जोड़े के लिए (2, 1), (3, 1), और ( 5, 4)।

कभी-कभी व्युत्क्रम को मानों के युग्म {{math|(''σ''''i'',''σ''''j'')}} के रूप में परिभाषित किया जाता है जिसका क्रम व्युत्क्रम होता है; इससे व्युत्क्रमों की संख्या पर कोई फर्क नहीं पड़ता है, और यह जोड़ी (व्युत्क्रम) भी व्युत्क्रम क्रमपरिवर्तन σ−1 के लिए उपरोक्त अर्थ में एक व्युत्क्रम है। व्युत्क्रम की संख्या उस डिग्री के लिए एक महत्वपूर्ण माप है जिस तक क्रमचय की प्रविष्टियाँ क्रम से बाहर हैं; यह σ और σ−1 के लिए समान है। K व्युत्क्रमों के साथ एक क्रमचय को क्रम में लाने के लिए (अर्थात, इसे पहचान क्रमपरिवर्तन में रूपांतरित करें), क्रमिक रूप से लागू करके (सही-गुणा द्वारा) आसन्न ट्रांसपोज़िशन, हमेशा संभव है और k ऐसे ऑपरेशनों के अनुक्रम की आवश्यकता होती है। इसके अलावा, आसन्न परिवर्तनों के लिए कोई भी उचित विकल्प काम करेगा: यह प्रत्येक चरण में i और {{nowrap|''i'' + 1}} का स्थानान्तरण चुनने के लिए पर्याप्त है जहाँ i अब तक संशोधित क्रमचय का अवतरण है (ताकि स्थानान्तरण इस विशेष वंश को हटा देगा, ~~हालांकि~~ यह अन्य अवरोही बना सकता है)। ऐसा इसलिए है क्योंकि इस तरह के ट्रांसपोजिशन को लागू करने से व्युत्क्रमों की संख्या 1 कम हो जाती है; जब तक यह संख्या शून्य नहीं है, तब तक क्रमपरिवर्तन पहचान नहीं है, इसलिए इसमें कम से कम एक वंश है। अनुक्रम को क्रम में रखने के लिए [[ बबल शॅाट |बबल शॅाट]] और [[ सम्मिलन सॉर्ट | सम्मिलन सॉर्ट]] को इस प्रक्रिया के विशेष उदाहरणों के रूप में व्याख्या किया जा सकता है। संयोग से यह प्रक्रिया सिद्ध करती है कि किसी भी क्रमचय σ को सन्निकट प्रतिस्थापनों के गुणनफल के रूप में लिखा जा सकता है; इसके लिए कोई ऐसे ट्रांसपोज़िशन के किसी भी क्रम को आसानी से उलट सकता है जो σ को पहचान में बदल देता है। वास्तव में, आसन्न ट्रांसपोज़िशन के सभी अनुक्रमों की गणना करके जो σ को पहचान में बदल देगा, एक (उलटने के बाद) न्यूनतम लंबाई के सभी अभिव्यक्तियों की एक पूरी सूची प्राप्त करता है, जो आसन्न ट्रांसपोज़िशन के उत्पाद के रूप में σ लिखते हैं।

कभी-कभी व्युत्क्रम को मानों के युग्म {{math|(''σ''''i'',''σ''''j'')}} के रूप में परिभाषित किया जाता है जिसका क्रम व्युत्क्रम होता है; इससे व्युत्क्रमों की संख्या पर कोई फर्क नहीं पड़ता है, और यह जोड़ी (व्युत्क्रम) भी व्युत्क्रम क्रमपरिवर्तन σ−1 के लिए उपरोक्त अर्थ में एक व्युत्क्रम है। व्युत्क्रम की संख्या उस डिग्री के लिए एक महत्वपूर्ण माप है जिस तक क्रमचय की प्रविष्टियाँ क्रम से बाहर हैं; यह σ और σ−1 के लिए समान है। K व्युत्क्रमों के साथ एक क्रमचय को क्रम में लाने के लिए (अर्थात, इसे पहचान क्रमपरिवर्तन में रूपांतरित करें), क्रमिक रूप से लागू करके (सही-गुणा द्वारा) आसन्न ट्रांसपोज़िशन, हमेशा संभव है और k ऐसे ऑपरेशनों के अनुक्रम की आवश्यकता होती है। इसके अलावा, आसन्न परिवर्तनों के लिए कोई भी उचित विकल्प काम करेगा: यह प्रत्येक चरण में i और {{nowrap|''i'' + 1}} का स्थानान्तरण चुनने के लिए पर्याप्त है जहाँ i अब तक संशोधित क्रमचय का अवतरण है (ताकि स्थानान्तरण इस विशेष वंश को हटा देगा, चूंकि यह अन्य अवरोही बना सकता है)। ऐसा इसलिए है क्योंकि इस तरह के ट्रांसपोजिशन को लागू करने से व्युत्क्रमों की संख्या 1 कम हो जाती है; जब तक यह संख्या शून्य नहीं है, तब तक क्रमपरिवर्तन पहचान नहीं है, इसलिए इसमें कम से कम एक वंश है। अनुक्रम को क्रम में रखने के लिए [[ बबल शॅाट |बबल शॅाट]] और [[ सम्मिलन सॉर्ट | सम्मिलन सॉर्ट]] को इस प्रक्रिया के विशेष उदाहरणों के रूप में व्याख्या किया जा सकता है। संयोग से यह प्रक्रिया सिद्ध करती है कि किसी भी क्रमचय σ को सन्निकट प्रतिस्थापनों के गुणनफल के रूप में लिखा जा सकता है; इसके लिए कोई ऐसे ट्रांसपोज़िशन के किसी भी क्रम को आसानी से उलट सकता है जो σ को पहचान में बदल देता है। वास्तव में, आसन्न ट्रांसपोज़िशन के सभी अनुक्रमों की गणना करके जो σ को पहचान में बदल देगा, एक (उलटने के बाद) न्यूनतम लंबाई के सभी अभिव्यक्तियों की एक पूरी सूची प्राप्त करता है, जो आसन्न ट्रांसपोज़िशन के उत्पाद के रूप में σ लिखते हैं।

k व्युत्क्रम के साथ n के क्रमचय की संख्या एक Mahonian संख्या द्वारा व्यक्त की जाती है,{{sfn|Bóna|2004|pp=43ff}} यह उत्पाद के विस्तार में Xk का गुणांक है<math display="block">\prod_{m=1}^n\sum_{i=0}^{m-1}X^i = 1 \left(1 + X\right)\left(1 + X + X^2\right) \cdots \left(1 + X + X^2 + \cdots + X^{n-1}\right),</math>जिसे q-फैक्टोरियल [n]q! . उत्पाद का विस्तार [[नेकलेस (कॉम्बिनेटरिक्स)]] में दिखाई देता है।

Line 352:

कंप्यूटिंग में मूल्यों के दिए गए अनुक्रम के क्रमपरिवर्तन उत्पन्न करने की आवश्यकता हो सकती है। ऐसा करने के लिए सर्वोत्तम रूप से अनुकूलित विधियां इस बात पर निर्भर करती हैं कि क्या कोई यादृच्छिक रूप से चुने गए क्रमपरिवर्तन चाहता है, या सभी क्रमपरिवर्तन, और बाद वाले मामले में यदि एक विशिष्ट आदेश की आवश्यकता होती है। एक अन्य प्रश्न यह है कि क्या दिए गए क्रम में प्रविष्टियों के बीच संभावित समानता को ध्यान में रखा जाना चाहिए; यदि ऐसा है, तो किसी को केवल अनुक्रम के अलग-अलग मल्टीसेट क्रमपरिवर्तन उत्पन्न करने चाहिए।

n के क्रमपरिवर्तन उत्पन्न करने का एक स्पष्ट तरीका लेहमर कोड के लिए मान उत्पन्न करना है (संभवतः n तक के पूर्णांकों के भाज्य संख्या प्रणाली प्रतिनिधित्व का उपयोग करके!), और उन्हें संबंधित क्रमपरिवर्तन में परिवर्तित करें। हालाँकि, बाद वाला कदम, जबकि सीधा है, कुशलता से लागू करना कठिन है, क्योंकि इसके लिए एक अनुक्रम से प्रत्येक चयन के लिए n संचालन की आवश्यकता होती है और इसे एक मनमाने स्थान पर हटा दिया जाता है; एक [[ सरणी डेटा संरचना |सरणी डेटा संरचना]] या एक [[ लिंक्ड सूची | लिंक्ड सूची]] के रूप में अनुक्रम के स्पष्ट प्रतिनिधित्व के लिए, रूपांतरण करने के लिए n2/4 संचालन के बारे में (विभिन्न कारणों से) दोनों की आवश्यकता होती है। n के छोटे होने की संभावना के साथ (विशेष रूप से यदि सभी क्रमपरिवर्तनों की पीढ़ी की आवश्यकता है) जो कि बहुत अधिक समस्या नहीं है, लेकिन यह पता चला है कि यादृच्छिक और व्यवस्थित पीढ़ी दोनों के लिए सरल विकल्प हैं जो काफी बेहतर करते हैं। इस कारण से यह उपयोगी प्रतीत नहीं होता है, ~~हालांकि~~ निश्चित रूप से संभव है, एक विशेष डेटा संरचना को नियोजित करने के लिए जो O(n log n) समय में लेह्मर कोड से क्रमचय में रूपांतरण करने की अनुमति देगा।

n के क्रमपरिवर्तन उत्पन्न करने का एक स्पष्ट तरीका लेहमर कोड के लिए मान उत्पन्न करना है (संभवतः n तक के पूर्णांकों के भाज्य संख्या प्रणाली प्रतिनिधित्व का उपयोग करके!), और उन्हें संबंधित क्रमपरिवर्तन में परिवर्तित करें। हालाँकि, बाद वाला कदम, जबकि सीधा है, कुशलता से लागू करना कठिन है, क्योंकि इसके लिए एक अनुक्रम से प्रत्येक चयन के लिए n संचालन की आवश्यकता होती है और इसे एक मनमाने स्थान पर हटा दिया जाता है; एक [[ सरणी डेटा संरचना |सरणी डेटा संरचना]] या एक [[ लिंक्ड सूची | लिंक्ड सूची]] के रूप में अनुक्रम के स्पष्ट प्रतिनिधित्व के लिए, रूपांतरण करने के लिए n2/4 संचालन के बारे में (विभिन्न कारणों से) दोनों की आवश्यकता होती है। n के छोटे होने की संभावना के साथ (विशेष रूप से यदि सभी क्रमपरिवर्तनों की पीढ़ी की आवश्यकता है) जो कि बहुत अधिक समस्या नहीं है, लेकिन यह पता चला है कि यादृच्छिक और व्यवस्थित पीढ़ी दोनों के लिए सरल विकल्प हैं जो काफी बेहतर करते हैं। इस कारण से यह उपयोगी प्रतीत नहीं होता है, चूंकि निश्चित रूप से संभव है, एक विशेष डेटा संरचना को नियोजित करने के लिए जो O(n log n) समय में लेह्मर कोड से क्रमचय में रूपांतरण करने की अनुमति देगा।

==== क्रमपरिवर्तन की यादृच्छिक पीढ़ी ====

~~'''n~~ मानों के दिए गए अनुक्रम के [[ ~~यादृच्छिक क्रमपरिवर्तन |~~ यादृच्छिक क्रमपरिवर्तन]] उत्पन्न करने के लिए, इससे कोई ~~फर्क~~ नहीं पड़ता है कि अनुक्रम में n का एक यादृच्छिक रूप से चयनित क्रमपरिवर्तन लागू ~~किया जाए~~, या अनुक्रम के विशिष्ट (मल्टीसेट) क्रमपरिवर्तनों के सेट से एक यादृच्छिक तत्व ~~का चयन किया जाए।~~ ऐसा इसलिए है, क्योंकि दोहराए गए मानों के मामले में n के कई अलग-अलग क्रमपरिवर्तन हो सकते हैं, जिसके परिणामस्वरूप एक ही अनुमत अनुक्रम होता है, ऐसे क्रमपरिवर्तन की संख्या प्रत्येक संभावित परिणाम के लिए समान होती है। व्यवस्थित पीढ़ी के विपरीत, जो संख्या n की वृद्धि के कारण बड़े n के लिए अक्षम्य हो ~~जाता~~ है!, यह मानने का कोई कारण नहीं है कि यादृच्छिक पीढ़ी के लिए n छोटा होगा।~~'''~~

एन मानों के दिए गए अनुक्रम के [[यादृच्छिक क्रमपरिवर्तन]] उत्पन्न करने के लिए, इससे कोई फ़र्क नहीं पड़ता कि कोई अनुक्रम में n का यादृच्छिक रूप से चयनित क्रमपरिवर्तन लागू करता है, या अनुक्रम के विशिष्ट (मल्टीसेट) क्रमपरिवर्तनों के सेट से एक यादृच्छिक तत्व चुनता है। ऐसा इसलिए है, क्योंकि दोहराए गए मानों के मामले में n के कई अलग-अलग क्रमपरिवर्तन हो सकते हैं, जिसके परिणामस्वरूप एक ही अनुमत अनुक्रम होता है, ऐसे क्रमपरिवर्तन की संख्या प्रत्येक संभावित परिणाम के लिए समान होती है। व्यवस्थित पीढ़ी के विपरीत, जो संख्या n की वृद्धि के कारण बड़े n के लिए अक्षम्य हो जाती है! यह मानने का कोई कारण नहीं है कि यादृच्छिक पीढ़ी के लिए n छोटा होगा।

एक यादृच्छिक क्रमचय उत्पन्न करने के लिए मूल विचार n! पूर्णांकों ~~का क्रम~~ d1,डी2,...,डी''n'' ~~संतुष्टि देने वाला~~ {{math|0 ≤ ''d''''i'' < ''i''}} (चूंकि डी1 हमेशा शून्य होता है इसे छोड़ा जा सकता है) और इसे एक विशेषण पत्राचार के माध्यम से क्रमचय में परिवर्तित करने के लिए। बाद के पत्राचार के लिए लेहमर कोड के रूप में (रिवर्स) अनुक्रम की व्याख्या की जा सकती है, और यह [[ रोनाल्ड फिशर ]] और [[ फ्रैंक येट्स ]] द्वारा पहली बार 1938 में प्रकाशित एक जनरेशन विधि देता है।<ref>{{cite book

एक यादृच्छिक क्रमचय उत्पन्न करने के लिए मूल विचार n! पूर्णांकों के अनुक्रम d1,d2,..., d''n'' संतोषजनक {{math|0 ≤ ''d''''i'' < ''i''}} (चूंकि d1 हमेशा शून्य होता है इसे छोड़ा जा सकता है) और इसे एक विशेषण पत्राचार के माध्यम से क्रमचय में परिवर्तित करने के लिए। बाद के पत्राचार के लिए लेहमर कोड के रूप में (रिवर्स) अनुक्रम की व्याख्या की जा सकती है, और यह [[ रोनाल्ड फिशर |रोनाल्ड फिशर]] और [[ फ्रैंक येट्स | फ्रैंक येट्स]] द्वारा पहली बार 1938 में प्रकाशित एक जनरेशन विधि देता है।<ref>{{cite book

|author1=Fisher, R.A. |author2=Yates, F. | title = जैविक, कृषि और चिकित्सा अनुसंधान के लिए सांख्यिकीय तालिकाएँ| orig-year = 1938

| edition = 3rd

Line 367:

| location = London

| oclc = 14222135

}}</ref>

जबकि उस समय कंप्यूटर कार्यान्वयन कोई समस्या नहीं थी, यह विधि लेह्मर कोड से क्रमचय में कुशलतापूर्वक परिवर्तित करने के लिए ऊपर स्केच की गई कठिनाई से ग्रस्त है। एक अलग विशेषण पत्राचार का उपयोग करके इसका उपचार किया जा सकता है: ~~d का उपयोग करने~~ के ~~बाद''~~i~~'' अनुक्रम के~~ शेष तत्वों (i के घटते मूल्यों के लिए) के बीच एक तत्व का चयन करने के लिए, तत्व को हटाने और ~~आगे के तत्वों~~ को एक स्थान पर स्थानांतरित करके अनुक्रम को संकुचित करने के बजाय, अंतिम शेष तत्व के साथ एक [[ स्वैप (कंप्यूटर विज्ञान) ]] ~~तत्व।~~ इस प्रकार चयन के लिए शेष तत्व समय के प्रत्येक बिंदु पर एक ~~क्रमागत~~ श्रेणी बनाते हैं, भले ही वे ~~मूल क्रम में~~ उसी क्रम में न हों, जैसा कि ~~उन्होंने किया था।~~ पूर्णांकों के ~~क्रम~~ से ~~क्रमपरिवर्तन~~ तक ~~का मानचित्रण~~ कुछ जटिल है, लेकिन ~~इसे~~ तत्काल [[ प्रेरण (गणित) ]] द्वारा प्रत्येक क्रमपरिवर्तन को ठीक एक तरह से उत्पन्न करने के लिए देखा जा सकता है। जब चयनित तत्व अंतिम शेष तत्व होता है, तो स्वैप ऑपरेशन को छोड़ा जा सकता है। ~~यह स्थिति~~ के लिए परीक्षण ~~की गारंटी देने~~ के लिए पर्याप्त रूप से अक्सर नहीं होता है, लेकिन अंतिम तत्व को चयन के उम्मीदवारों के बीच शामिल किया जाना चाहिए, यह ~~सुनिश्चित करने~~ के लिए कि सभी क्रमपरिवर्तन उत्पन्न किए जा सकते हैं।

जबकि उस समय कंप्यूटर कार्यान्वयन कोई समस्या नहीं थी, यह विधि लेह्मर कोड से क्रमचय में कुशलतापूर्वक परिवर्तित करने के लिए ऊपर स्केच की गई कठिनाई से ग्रस्त है। एक अलग विशेषण पत्राचार का उपयोग करके इसका उपचार किया जा सकता है: अनुक्रम के i शेष तत्वों (i के घटते मूल्यों के लिए) के बीच एक तत्व का चयन करने के लिए di का उपयोग करने के बाद, तत्व को हटाने और अनुक्रम को एक स्थान पर स्थानांतरित करके अनुक्रम को संकुचित करने के बजाय, अंतिम शेष तत्व के साथ तत्व को [[ स्वैप (कंप्यूटर विज्ञान) |स्वैप (कंप्यूटर विज्ञान)]] करता है। इस प्रकार चयन के लिए शेष तत्व समय के प्रत्येक बिंदु पर एक सतत श्रेणी बनाते हैं, भले ही वे उसी क्रम में न हों जैसा कि वे मूल अनुक्रम में थे। पूर्णांकों के अनुक्रम से क्रमचय तक की मैपिंग कुछ जटिल है, लेकिन यह देखा जा सकता है कि प्रत्येक क्रमचय को ठीक एक तरह से उत्पन्न किया जा सकता है, एक तत्काल [[ प्रेरण (गणित) |प्रेरण (गणित)]] द्वारा। जब चयनित तत्व अंतिम शेष तत्व होता है, तो स्वैप ऑपरेशन छोड़ा जा सकता है। हालत के लिए वारंट परीक्षण के लिए यह पर्याप्त रूप से अक्सर नहीं होता है, लेकिन अंतिम तत्व को चयन के उम्मीदवारों के बीच शामिल किया जाना चाहिए, यह गारंटी देने के लिए कि सभी क्रमपरिवर्तन उत्पन्न किए जा सकते हैं।

~~का एक यादृच्छिक क्रमपरिवर्तन उत्पन्न करने के लिए परिणामी एल्गोरिथ्म~~ <code>''a''[0], ''a''[1], ..., ''a''[''n'' − 1]</code> [[ स्यूडोकोड ]] में निम्नानुसार वर्णित किया जा सकता है:

<code>''a''[0], ''a''[1], ..., ''a''[''n'' − 1]</code> का एक यादृच्छिक क्रमचय उत्पन्न करने के लिए परिणामी एल्गोरिथम को [[ स्यूडोकोड |स्यूडोकोड]] में निम्नानुसार वर्णित किया जा सकता है:

''i'' ~~के लिए~~ ''n'' से downto 2 ~~करना~~

'''for''' ''i'' '''from''' ''n'' '''downto''' 2 '''do'''

''डीi← {0, ..., i − 1} ~~का यादृच्छिक अवयव~~

''di'' ← random element of { 0, ..., ''i'' − 1 }

~~'स्वैप' ए [डीi] और एक[i - 1]~~

'''swap''' ''a''[''di''] and ''a''[''i'' − 1]

इसे सरणी के आरंभीकरण के साथ जोड़ा जा सकता है <code>''a''[''i''] = ''i''</code> निम्नलिखित नुसार

'''for''' ''i'' '''from''' 0 '''to''' ''n''−1 '''do'''

''di''+1 ← random element of { 0, ..., ''i'' }

''a''[''i''] ← ''a''[''di''+1]

''i'' ~~के लिए 0 से ''n''−1 do . तक~~

''a''[''di''+1] ← ''i''

~~''डी~~''''i~~''+1~~ ~~← यादृच्छिक अवयव {0, ..., i }~~

अगर d''i''+1 = i, पहला असाइनमेंट एक गैर-आरंभिक मान की नकल करेगा, लेकिन दूसरा इसे सही मान i के साथ अधिलेखित कर देगा।

~~एक [मैं] ← एक [डी~~~~''i''~~+1]

~~एक [डी~~''i''~~+1] ← मैं~~

अगर डी''i''+1 = i, पहला असाइनमेंट एक गैर-आरंभिक मान की नकल करेगा, लेकिन दूसरा इसे सही मान i के साथ अधिलेखित कर देगा।

~~हालांकि~~, फिशर-येट्स ~~क्रमपरिवर्तन~~ उत्पन्न करने के लिए सबसे तेज़ ~~एल्गोरिदम~~ नहीं है, क्योंकि फिशर-येट्स अनिवार्य रूप से अनुक्रमिक ~~एल्गोरिदम~~ है और ~~प्रक्रियाओं को विभाजित~~ और ~~जीत~~ समानांतर में समान परिणाम प्राप्त कर ~~सकते~~ हैं।<ref>{{cite news|author1=Bacher, A. |author2=Bodini, O.|author3=Hwang, H.K.|author4=Tsai, T.H. | title = कॉइन टॉसिंग द्वारा यादृच्छिक क्रमपरिवर्तन उत्पन्न करना: शास्त्रीय एल्गोरिदम, नया विश्लेषण और आधुनिक कार्यान्वयन।| edition = ACM Trans. Algorithms 13(2): 24:1–24:43

चूंकि, फिशर-येट्स क्रमचय उत्पन्न करने के लिए सबसे तेज़ एल्गोरिथम नहीं है, क्योंकि फिशर-येट्स अनिवार्य रूप से एक अनुक्रमिक एल्गोरिथम है और "फूट डालो और जीतो" प्रक्रियाएं समानांतर में समान परिणाम प्राप्त कर सकती हैं।<ref>{{cite news|author1=Bacher, A. |author2=Bodini, O.|author3=Hwang, H.K.|author4=Tsai, T.H. | title = कॉइन टॉसिंग द्वारा यादृच्छिक क्रमपरिवर्तन उत्पन्न करना: शास्त्रीय एल्गोरिदम, नया विश्लेषण और आधुनिक कार्यान्वयन।| edition = ACM Trans. Algorithms 13(2): 24:1–24:43

| year = 2017

| pages = 24–43

}}</ref>

==== शब्दावली क्रम में पीढ़ी ====

किसी दिए गए अनुक्रम के सभी ~~क्रमपरिवर्तन~~ को व्यवस्थित रूप से उत्पन्न करने के कई तरीके हैं।<ref name=sedegewick1977>{{cite journal

किसी दिए गए अनुक्रम के सभी क्रमचयों को व्यवस्थित रूप से उत्पन्न करने के कई तरीके हैं।<ref name="sedegewick1977">{{cite journal

|last=Sedgewick|first=R

|title=क्रमपरिवर्तन पीढ़ी के तरीके|journal=Computing Surveys|year=1977|volume=9

Line 400:

Line 398:

|doi=10.1145/356689.356692

|s2cid=12139332

}}</ref>

}}</ref> एक क्लासिक, सरल, और लचीला एल्गोरिदम [[ लेक्सिकोग्राफिक ऑर्डरिंग ]] में अगले क्रमचय को खोजने पर आधारित है, यदि यह मौजूद है। यह दोहराए गए मानों को संभाल सकता है, जिस स्थिति के लिए यह एक बार प्रत्येक विशिष्ट मल्टीसेट क्रमचय उत्पन्न करता है। यहां तक कि साधारण क्रमपरिवर्तन के लिए भी यह लेह्मर कोड के लिए कोशीय क्रम में मान उत्पन्न करने (संभवत: भाज्य संख्या प्रणाली का उपयोग करके) और उन्हें क्रमपरिवर्तन में परिवर्तित करने की तुलना में काफी अधिक कुशल है। यह अनुक्रम को (कमजोर) बढ़ते हुए क्रम में क्रमबद्ध करके शुरू होता है (जो इसके लेक्सिकोग्राफिक रूप से न्यूनतम क्रमपरिवर्तन देता है), और तब तक अगले क्रमचय के लिए आगे बढ़ना दोहराता है जब तक कि एक मिल जाता है। यह पद्धति 14वीं शताब्दी के भारत में [[ नारायणा पंडित | नारायणा पंडित]] के पास वापस चली जाती है, और इसे बार-बार फिर से खोजा गया है।{{sfn|Knuth|2005|pp=1–26}}

एक क्लासिक, सरल और लचीला ~~एल्गोरिथम~~ [[ लेक्सिकोग्राफिक ऑर्डरिंग ]] में अगले ~~क्रमपरिवर्तन~~ को खोजने पर आधारित है, यदि यह मौजूद है। यह दोहराए गए मानों को संभाल सकता है, जिस स्थिति के लिए यह प्रत्येक विशिष्ट मल्टीसेट ~~क्रमपरिवर्तन को एक बार~~ उत्पन्न करता है। यहां तक ~~कि सामान्य~~ क्रमपरिवर्तन के लिए भी यह ~~लेहमर~~ कोड के लिए ~~लेक्सिकोग्राफिक~~ क्रम में मान उत्पन्न करने (~~संभवतः फैक्टोरियल नंबर सिस्टम~~ का उपयोग करके) और उन्हें क्रमपरिवर्तन में परिवर्तित करने की तुलना में काफी अधिक कुशल है। यह अनुक्रम को (कमजोर ~~रूप से~~) बढ़ते क्रम में क्रमबद्ध करके शुरू होता है (जो ~~इसकी शब्दावली में~~ न्यूनतम क्रमपरिवर्तन देता है), और तब तक अगले ~~क्रमपरिवर्तन~~ के लिए आगे ~~बढ़ते हुए~~ दोहराता है जब तक कि एक ~~पाया~~ जाता है। यह ~~विधि~~ 14वीं शताब्दी के भारत में [[ नारायणा पंडित ]]~~ा से मिलती~~ है, और इसे बार-बार खोजा गया है।{{sfn|Knuth|2005|pp=1–26}}

निम्नलिखित एल्गोरिथम ~~किसी~~ दिए गए ~~क्रमपरिवर्तन~~ के बाद अगले क्रमचय को लेक्सिकोग्राफिक रूप से उत्पन्न करता है। यह दिए गए ~~क्रमपरिवर्तन~~ को ~~जगह-जगह~~ बदल देता है।

निम्नलिखित एल्गोरिथम दिए गए क्रमचय के बाद अगले क्रमचय को लेक्सिकोग्राफिक रूप से उत्पन्न करता है। यह दिए गए क्रमचय को यथास्थान बदल देता है।

# सबसे बड़ा सूचकांक k ~~इस प्रकार~~ ज्ञात कीजिए कि {{nowrap|''a''[''k''] < ''a''[''k'' + 1]}}. यदि ऐसा कोई सूचकांक मौजूद नहीं है, तो क्रमचय अंतिम ~~क्रमपरिवर्तन~~ है।

# सबसे बड़ा सूचकांक k ज्ञात कीजिए जैसे कि {{nowrap|''a''[''k''] < ''a''[''k'' + 1]}}। यदि ऐसा कोई सूचकांक मौजूद नहीं है, क्रमचय अंतिम क्रमचय है।

# k से बड़ा सबसे बड़ा सूचकांक l ~~इस प्रकार~~ ज्ञात करें कि {{nowrap|''a''[''k''] < ''a''[''l'']}}.

# k से बड़ा सबसे बड़ा सूचकांक l ज्ञात करें जैसे कि {{nowrap|''a''[''k''] < ''a''[''l'']}}।

# a[k] के मान को a[l] ~~के साथ स्वैप करें।~~

# a[k] के मान को a[l] से बदलें।

# ए [के + 1] से ~~अनुक्रम को~~ उलट दें और अंतिम तत्व ए [एन] को शामिल ~~करें।~~

# अनुक्रम को a[k + 1] से उलट दें और अंतिम तत्व a[n] को शामिल कर लें।

उदाहरण के लिए, अनुक्रम [1, 2, 3, 4] (जो बढ़ते क्रम में है) ~~दिया गया है~~, और यह देखते हुए कि सूचकांक शून्य-आधारित ~~संख्या~~ है~~|शून्य-आधारित~~, चरण इस प्रकार हैं:

उदाहरण के लिए, दिया ग�

Anonymous

Search

क्रमचय: Difference between revisions

Namespaces

More

Page actions

@@ Line 166: / Line 166: @@
 === दोहराव के साथ क्रमपरिवर्तन ===
-समुच्चय S के k तत्वों की क्रमबद्ध व्यवस्था, जहाँ पुनरावृत्ति की अनुमति है, k-टपल्स  कहलाती हैं। उन्हें कभी-कभी पुनरावृत्ति के साथ क्रमपरिवर्तन के रूप में संदर्भित किया जाता है, हालांकि वे सामान्य रूप से क्रमपरिवर्तन नहीं होते हैं। उन्हें कुछ संदर्भों में अक्षर S पर शब्द भी कहा जाता है। यदि समुच्चय S में n अवयव हैं, तो S पर k-टपल्स  की संख्या <math>n^k.</math> कोई तत्व k-टपल में कितनी बार प्रकट हो सकता है, इस पर कोई प्रतिबंध नहीं है, लेकिन यदि कोई तत्व कितनी बार दिखाई दे सकता है, इस पर प्रतिबंध लगाया जाता है, तो यह सूत्र अब मान्य नहीं है।
+समुच्चय S के k तत्वों की क्रमबद्ध व्यवस्था, जहाँ पुनरावृत्ति की अनुमति है, k-टपल्स  कहलाती हैं। उन्हें कभी-कभी पुनरावृत्ति के साथ क्रमपरिवर्तन के रूप में संदर्भित किया जाता है, चूंकि वे सामान्य रूप से क्रमपरिवर्तन नहीं होते हैं। उन्हें कुछ संदर्भों में अक्षर S पर शब्द भी कहा जाता है। यदि समुच्चय S में n अवयव हैं, तो S पर k-टपल्स  की संख्या <math>n^k.</math> कोई तत्व k-टपल में कितनी बार प्रकट हो सकता है, इस पर कोई प्रतिबंध नहीं है, लेकिन यदि कोई तत्व कितनी बार दिखाई दे सकता है, इस पर प्रतिबंध लगाया जाता है, तो यह सूत्र अब मान्य नहीं है।
 === मल्टीसेट्स के क्रमपरिवर्तन ===
@@ Line 214: / Line 214: @@
 {{main|एक क्रमचय की समानता}}
-परिमित समुच्चय के प्रत्येक क्रमचय को स्थानान्तरण के गुणनफल के रूप में व्यक्त किया जा सकता है। [36] हालांकि एक दिए गए क्रमचय के लिए ऐसे कई व्यंजक मौजूद हो सकते हैं, या तो उन सभी में ट्रांसपोज़िशन की एक समान संख्या होती है या उन सभी में विषम संख्या में ट्रांसपोज़िशन होते हैं। इस प्रकार सभी क्रमचयों को इस संख्या के आधार पर [[सम या विषम के रूप में वर्गीकृत]] किया जा सकता है।
+परिमित समुच्चय के प्रत्येक क्रमचय को स्थानान्तरण के गुणनफल के रूप में व्यक्त किया जा सकता है। [36] चूंकि एक दिए गए क्रमचय के लिए ऐसे कई व्यंजक मौजूद हो सकते हैं, या तो उन सभी में ट्रांसपोज़िशन की एक समान संख्या होती है या उन सभी में विषम संख्या में ट्रांसपोज़िशन होते हैं। इस प्रकार सभी क्रमचयों को इस संख्या के आधार पर [[सम या विषम के रूप में वर्गीकृत]] किया जा सकता है।
 इस परिणाम को बढ़ाया जा सकता है ताकि प्रत्येक क्रमचय के लिए <math>\operatorname{sgn}\sigma</math> लिखा हुआ एक चिह्न निर्दिष्ट किया जा सके। <math>\operatorname{sgn}\sigma = +1</math> अगर <math>\sigma</math> सम है और <math>\operatorname{sgn}\sigma = -1</math> यदि <math>\sigma</math> विषम है। फिर दो क्रमपरिवर्तन के लिए <math>\sigma</math> तथा <math>\pi</math>
@@ Line 239: / Line 239: @@
 n के क्रमचय σ का आरोहण कोई भी स्थिति i < n है जहां निम्न मान वर्तमान मान से बड़ा है। अर्थात, यदि σ = σ1σ2...σn, तो i एक आरोहण है यदि σi < σi+1। उदाहरण के लिए, क्रमपरिवर्तन 3452167 में आरोही (स्थितियों पर) 1, 2, 5 और 6 हैं। इसी तरह, एक डिसेंट i < n के साथ σi > σi+1 की स्थिति है, इसलिए <math>1 \leq i<n</math> के साथ हर i या तो एक आरोही है या एक डिसेंट है σ। क्रमचय का एक आरोही क्रम क्रमचय का एक गैर-खाली बढ़ता हुआ सन्निकट क्रम है जिसे किसी भी छोर पर विस्तारित नहीं किया जा सकता है; यह लगातार चढ़ाई के अधिकतम अनुक्रम से मेल खाता है (उत्तरार्द्ध खाली हो सकता है: दो लगातार अवरोही के बीच अभी भी लंबाई 1 का आरोही रन है)। इसके विपरीत एक क्रमचय का एक बढ़ता क्रम आवश्यक रूप से सन्निहित नहीं है: यह कुछ स्थितियों पर मानों को छोड़ कर क्रमचय से प्राप्त तत्वों का बढ़ता क्रम है। उदाहरण के लिए, क्रमचय 2453167 में आरोही रन 245, 3, और 167 हैं, जबकि इसके बढ़ते क्रमांक 2367 हैं। यदि एक क्रमचय में k - 1 अवरोही है, तो यह k आरोही रन का संघ होना चाहिए।{{sfn|Bóna|2004|p=4f}}
-k आरोही के साथ n के क्रमपरिवर्तन की संख्या है (परिभाषा के अनुसार) यूलेरियन संख्या <math>\textstyle\left\langle{n\atop k}\right\rangle</math> सही\rangle; यह k अवरोही के साथ n के क्रमचय की संख्या भी है। हालांकि कुछ लेखक ऑयलेरियन संख्या <math>\textstyle\left\langle{n\atop k}\right\rangle</math> को k के साथ क्रमपरिवर्तन की संख्या के रूप में परिभाषित करते हैं। आरोही रन, जो {{nowrap|''k'' − 1}} अवरोही के अनुरूप है।{{sfn|Bona|2012|pages=4–5}} क्रमचय σ1σ2...σn की अधिकता एक सूचकांक j है जैसे कि {{nowrap|''σ''<sub>''j''</sub> > ''j''}}. यदि असमानता सख्त नहीं है (अर्थात, {{nowrap|''σ''<sub>''j''</sub> ≥ ''j''}}), तो j को एक कमजोर अतिरेक कहा जाता है। k अधिकता वाले n-क्रमपरिवर्तन की संख्या k अवरोही के साथ n-क्रमपरिवर्तन की संख्या के साथ मेल खाती है।{{sfn|Bona|2012|page=25}}
+k आरोही के साथ n के क्रमपरिवर्तन की संख्या है (परिभाषा के अनुसार) यूलेरियन संख्या <math>\textstyle\left\langle{n\atop k}\right\rangle</math> सही\rangle; यह k अवरोही के साथ n के क्रमचय की संख्या भी है। चूंकि कुछ लेखक ऑयलेरियन संख्या <math>\textstyle\left\langle{n\atop k}\right\rangle</math> को k के साथ क्रमपरिवर्तन की संख्या के रूप में परिभाषित करते हैं। आरोही रन, जो {{nowrap|''k'' − 1}} अवरोही के अनुरूप है।{{sfn|Bona|2012|pages=4–5}} क्रमचय σ1σ2...σn की अधिकता एक सूचकांक j है जैसे कि {{nowrap|''σ''<sub>''j''</sub> > ''j''}}. यदि असमानता सख्त नहीं है (अर्थात, {{nowrap|''σ''<sub>''j''</sub> ≥ ''j''}}), तो j को एक कमजोर अतिरेक कहा जाता है। k अधिकता वाले n-क्रमपरिवर्तन की संख्या k अवरोही के साथ n-क्रमपरिवर्तन की संख्या के साथ मेल खाती है।{{sfn|Bona|2012|page=25}}
 === फोटा का संक्रमण लेम्मा ===
@@ Line 246: / Line 246: @@
 चलो <math>f(p)=q</math> कोष्ठक-मिटाने वाला परिवर्तन हो जो <math>q</math> को एक-पंक्ति नोटेशन में लौटाता है <math>p</math> विहित में चक्र अंकन। जैसा कि कहा गया है, <math>f</math>  सभी कोष्ठकों को हटाकर संचालित होता है। व्युत्क्रम परिवर्तन का संचालन, {<math>f^{-1}(q)=p</math>,  जो एक-पंक्ति संकेतन में <math>q</math> दिए जाने पर विहित चक्र संकेतन में <math>p</math> लौटाता है, यह थोड़ा कम सहज है। <math>q = q_1q_2\cdots q_n</math> का पहला चक्र p}p विहित चक्र संकेतन में <math>q_1</math> से शुरू होना चाहिए। जब तक बाद के तत्व <math>q_1</math> से छोटे हैं, हम <math>p</math> के समान चक्र में हैं। <math>p</math> का दूसरा चक्र सबसे छोटे इंडेक्स <math>j</math> से शुरू होता है, जैसे कि <math>q_j > q_1</math>। दूसरे शब्दों में, <math>q_j</math> अपने बायीं ओर की सभी चीज़ों से बड़ा है, इसलिए इसे बाएँ से दाएँ अधिकतम कहा जाता है। कैनोनिकल चक्र संकेतन में प्रत्येक चक्र बाएं से दाएं अधिकतम के साथ शुरू होता है।{{sfn|Bona|2012|pp=109–110}}
-उदाहरण के लिए, क्रमचय में <math>q=312548976</math>, 5 पहला तत्व है जो प्रारंभिक तत्व 3 से बड़ा है, इसलिए <math>p</math> का पहला चक्र <math>(\,3\,1\,2\,)</math> होना चाहिए। फिर 8 अगला तत्व 5 से बड़ा है, तो दूसरा चक्र है <math>(\,5\,4\,)</math>। चूँकि 9, 8 से बड़ा है, <math>(\,8\,)</math> अपने आप में एक चक्र है। अंत में, 9 अपने दाहिनी ओर शेष सभी तत्वों से बड़ा है, इसलिए अंतिम चक्र है {\displaystyle (\,9\,7\,6\,)}{\displaystyle (\,9\,7\,6\,)}। इन 4 चक्रों को जोड़ने पर <math>p=(\,3\,1\,2\,)(\,5\,4\,)(\,8\,)(\,9\,7\,6\,)</math> विहित चक्र अंकन में।
+उदाहरण के लिए, क्रमचय में <math>q=312548976</math>, 5 पहला तत्व है जो प्रारंभिक तत्व 3 से बड़ा है, इसलिए <math>p</math> का पहला चक्र <math>(\,3\,1\,2\,)</math> होना चाहिए। फिर 8 अगला तत्व 5 से बड़ा है, तो दूसरा चक्र है <math>(\,5\,4\,)</math>। चूँकि 9, 8 से बड़ा है, <math>(\,8\,)</math> अपने आप में एक चक्र है। अंत में, 9 अपने दाहिनी ओर शेष सभी तत्वों से बड़ा है, इसलिए अंतिम चक्र है (9,7,6)। इन 4 चक्रों को जोड़ने पर <math>p=(\,3\,1\,2\,)(\,5\,4\,)(\,8\,)(\,9\,7\,6\,)</math> विहित चक्र अंकन में।
 निम्न तालिका <math>q</math> और <math>p</math> दोनों को <math>123</math> के छह क्रमपरिवर्तनों के लिए दिखाती है। प्रत्येक समानता का बोल्ड पक्ष अपने नामित संकेतन <math>q</math> के लिए एक-पंक्ति संकेतन और <math>p</math> के लिए विहित चक्र संकेतन) का उपयोग करके क्रमपरिवर्तन दिखाता है, जबकि गैर-बोल्ड पक्ष दूसरे में समान क्रमचय दिखाता है अंकन। तालिका के प्रत्येक स्तंभ के बोल्ड पक्ष की तुलना करने से फोटा के आक्षेप के संचालन को हटाने/पुनर्स्थापना करने वाले कोष्ठक को दर्शाता है, प्रत्येक स्तंभ के एक ही पक्ष की तुलना करते समय (उदाहरण के लिए, बायाँ पक्ष) दिखाता है कौन से क्रमपरिवर्तन खुद को बायजेक्शन (पहली 3 पंक्तियों) द्वारा मैप किए जाते हैं और कौन से नहीं हैं (अंतिम 3 पंक्तियाँ)।
@@ Line 282: / Line 282: @@
 }}</ref>]]क्रमपरिवर्तन σ का व्युत्क्रम पदों की एक जोड़ी (i, j) है जहां क्रमचय की प्रविष्टियां विपरीत क्रम में होती हैं: <math>\sigma_i > \sigma_j</math>{{sfn|Bóna|2004|p=43}}  तो <math>i < j</math>  दो आसन्न स्थितियों पर एक व्युत्क्रम है। उदाहरण के लिए, क्रमपरिवर्तन σ = 23154 में तीन व्युत्क्रम हैं: (1, 3), (2, 3), और (4, 5), प्रविष्टियों के जोड़े के लिए (2, 1), (3, 1), और ( 5, 4)।
-कभी-कभी व्युत्क्रम को मानों के युग्म {{math|(''σ''<sub>''i''</sub>,''σ''<sub>''j''</sub>)}} के रूप में परिभाषित किया जाता है जिसका क्रम व्युत्क्रम होता है; इससे व्युत्क्रमों की संख्या पर कोई फर्क नहीं पड़ता है, और यह जोड़ी (व्युत्क्रम) भी व्युत्क्रम क्रमपरिवर्तन σ<sup>−1</sup> के लिए उपरोक्त अर्थ में एक व्युत्क्रम है। व्युत्क्रम की संख्या उस डिग्री के लिए एक महत्वपूर्ण माप है जिस तक क्रमचय की प्रविष्टियाँ क्रम से बाहर हैं; यह σ और σ<sup>−1</sup> के लिए समान है। K व्युत्क्रमों के साथ एक क्रमचय को क्रम में लाने के लिए (अर्थात, इसे पहचान क्रमपरिवर्तन में रूपांतरित करें), क्रमिक रूप से लागू करके (सही-गुणा द्वारा) आसन्न ट्रांसपोज़िशन, हमेशा संभव है और k ऐसे ऑपरेशनों के अनुक्रम की आवश्यकता होती है। इसके अलावा, आसन्न परिवर्तनों के लिए कोई भी उचित विकल्प काम करेगा:  यह प्रत्येक चरण में i और {{nowrap|''i'' + 1}} का स्थानान्तरण चुनने के लिए पर्याप्त है जहाँ i अब तक संशोधित क्रमचय का अवतरण है (ताकि स्थानान्तरण इस विशेष वंश को हटा देगा, हालांकि यह अन्य अवरोही बना सकता है)। ऐसा इसलिए है क्योंकि इस तरह के ट्रांसपोजिशन को लागू करने से व्युत्क्रमों की संख्या 1 कम हो जाती है; जब तक यह संख्या शून्य नहीं है, तब तक क्रमपरिवर्तन पहचान नहीं है, इसलिए इसमें कम से कम एक वंश है। अनुक्रम को क्रम में रखने के लिए [[ बबल शॅाट |बबल शॅाट]] और [[ सम्मिलन सॉर्ट | सम्मिलन सॉर्ट]] को इस प्रक्रिया के विशेष उदाहरणों के रूप में व्याख्या किया जा सकता है। संयोग से यह प्रक्रिया सिद्ध करती है कि किसी भी क्रमचय σ को सन्निकट प्रतिस्थापनों के गुणनफल के रूप में लिखा जा सकता है; इसके लिए कोई ऐसे ट्रांसपोज़िशन के किसी भी क्रम को आसानी से उलट सकता है जो σ को पहचान में बदल देता है। वास्तव में, आसन्न ट्रांसपोज़िशन के सभी अनुक्रमों की गणना करके जो σ को पहचान में बदल देगा, एक (उलटने के बाद) न्यूनतम लंबाई के सभी अभिव्यक्तियों की एक पूरी सूची प्राप्त करता है, जो आसन्न ट्रांसपोज़िशन के उत्पाद के रूप में σ लिखते हैं।
+कभी-कभी व्युत्क्रम को मानों के युग्म {{math|(''σ''<sub>''i''</sub>,''σ''<sub>''j''</sub>)}} के रूप में परिभाषित किया जाता है जिसका क्रम व्युत्क्रम होता है; इससे व्युत्क्रमों की संख्या पर कोई फर्क नहीं पड़ता है, और यह जोड़ी (व्युत्क्रम) भी व्युत्क्रम क्रमपरिवर्तन σ<sup>−1</sup> के लिए उपरोक्त अर्थ में एक व्युत्क्रम है। व्युत्क्रम की संख्या उस डिग्री के लिए एक महत्वपूर्ण माप है जिस तक क्रमचय की प्रविष्टियाँ क्रम से बाहर हैं; यह σ और σ<sup>−1</sup> के लिए समान है। K व्युत्क्रमों के साथ एक क्रमचय को क्रम में लाने के लिए (अर्थात, इसे पहचान क्रमपरिवर्तन में रूपांतरित करें), क्रमिक रूप से लागू करके (सही-गुणा द्वारा) आसन्न ट्रांसपोज़िशन, हमेशा संभव है और k ऐसे ऑपरेशनों के अनुक्रम की आवश्यकता होती है। इसके अलावा, आसन्न परिवर्तनों के लिए कोई भी उचित विकल्प काम करेगा:  यह प्रत्येक चरण में i और {{nowrap|''i'' + 1}} का स्थानान्तरण चुनने के लिए पर्याप्त है जहाँ i अब तक संशोधित क्रमचय का अवतरण है (ताकि स्थानान्तरण इस विशेष वंश को हटा देगा, चूंकि यह अन्य अवरोही बना सकता है)। ऐसा इसलिए है क्योंकि इस तरह के ट्रांसपोजिशन को लागू करने से व्युत्क्रमों की संख्या 1 कम हो जाती है; जब तक यह संख्या शून्य नहीं है, तब तक क्रमपरिवर्तन पहचान नहीं है, इसलिए इसमें कम से कम एक वंश है। अनुक्रम को क्रम में रखने के लिए [[ बबल शॅाट |बबल शॅाट]] और [[ सम्मिलन सॉर्ट | सम्मिलन सॉर्ट]] को इस प्रक्रिया के विशेष उदाहरणों के रूप में व्याख्या किया जा सकता है। संयोग से यह प्रक्रिया सिद्ध करती है कि किसी भी क्रमचय σ को सन्निकट प्रतिस्थापनों के गुणनफल के रूप में लिखा जा सकता है; इसके लिए कोई ऐसे ट्रांसपोज़िशन के किसी भी क्रम को आसानी से उलट सकता है जो σ को पहचान में बदल देता है। वास्तव में, आसन्न ट्रांसपोज़िशन के सभी अनुक्रमों की गणना करके जो σ को पहचान में बदल देगा, एक (उलटने के बाद) न्यूनतम लंबाई के सभी अभिव्यक्तियों की एक पूरी सूची प्राप्त करता है, जो आसन्न ट्रांसपोज़िशन के उत्पाद के रूप में σ लिखते हैं।
 k व्युत्क्रम के साथ n के क्रमचय की संख्या एक Mahonian संख्या द्वारा व्यक्त की जाती है,{{sfn|Bóna|2004|pp=43ff}} यह उत्पाद के विस्तार में X<sup>k</sup> का गुणांक है<math display="block">\prod_{m=1}^n\sum_{i=0}^{m-1}X^i = 1 \left(1 + X\right)\left(1 + X + X^2\right) \cdots \left(1 + X + X^2 + \cdots + X^{n-1}\right),</math>जिसे q-फैक्टोरियल [n]q! . उत्पाद का विस्तार [[नेकलेस (कॉम्बिनेटरिक्स)]] में दिखाई देता है।
@@ Line 352: / Line 352: @@
 कंप्यूटिंग में मूल्यों के दिए गए अनुक्रम के क्रमपरिवर्तन उत्पन्न करने की आवश्यकता हो सकती है। ऐसा करने के लिए सर्वोत्तम रूप से अनुकूलित विधियां इस बात पर निर्भर करती हैं कि क्या कोई यादृच्छिक रूप से चुने गए क्रमपरिवर्तन चाहता है, या सभी क्रमपरिवर्तन, और बाद वाले मामले में यदि एक विशिष्ट आदेश की आवश्यकता होती है। एक अन्य प्रश्न यह है कि क्या दिए गए क्रम में प्रविष्टियों के बीच संभावित समानता को ध्यान में रखा जाना चाहिए; यदि ऐसा है, तो किसी को केवल अनुक्रम के अलग-अलग मल्टीसेट क्रमपरिवर्तन उत्पन्न करने चाहिए।
-n के क्रमपरिवर्तन उत्पन्न करने का एक स्पष्ट तरीका लेहमर कोड के लिए मान उत्पन्न करना है (संभवतः n तक के पूर्णांकों के भाज्य संख्या प्रणाली प्रतिनिधित्व का उपयोग करके!), और उन्हें संबंधित क्रमपरिवर्तन में परिवर्तित करें। हालाँकि, बाद वाला कदम, जबकि सीधा है, कुशलता से लागू करना कठिन है, क्योंकि इसके लिए एक अनुक्रम से प्रत्येक चयन के लिए n संचालन की आवश्यकता होती है और इसे एक मनमाने स्थान पर हटा दिया जाता है; एक [[ सरणी डेटा संरचना |सरणी डेटा संरचना]] या एक [[ लिंक्ड सूची | लिंक्ड सूची]] के रूप में अनुक्रम के स्पष्ट प्रतिनिधित्व के लिए, रूपांतरण करने के लिए n<sub>2/4</sub> संचालन के बारे में (विभिन्न कारणों से) दोनों की आवश्यकता होती है। n के छोटे होने की संभावना के साथ (विशेष रूप से यदि सभी क्रमपरिवर्तनों की पीढ़ी की आवश्यकता है) जो कि बहुत अधिक समस्या नहीं है, लेकिन यह पता चला है कि यादृच्छिक और व्यवस्थित पीढ़ी दोनों के लिए सरल विकल्प हैं जो काफी बेहतर करते हैं। इस कारण से यह उपयोगी प्रतीत नहीं होता है, हालांकि निश्चित रूप से संभव है, एक विशेष डेटा संरचना को नियोजित करने के लिए जो O(n log n) समय में लेह्मर कोड से क्रमचय में रूपांतरण करने की अनुमति देगा।
+n के क्रमपरिवर्तन उत्पन्न करने का एक स्पष्ट तरीका लेहमर कोड के लिए मान उत्पन्न करना है (संभवतः n तक के पूर्णांकों के भाज्य संख्या प्रणाली प्रतिनिधित्व का उपयोग करके!), और उन्हें संबंधित क्रमपरिवर्तन में परिवर्तित करें। हालाँकि, बाद वाला कदम, जबकि सीधा है, कुशलता से लागू करना कठिन है, क्योंकि इसके लिए एक अनुक्रम से प्रत्येक चयन के लिए n संचालन की आवश्यकता होती है और इसे एक मनमाने स्थान पर हटा दिया जाता है; एक [[ सरणी डेटा संरचना |सरणी डेटा संरचना]] या एक [[ लिंक्ड सूची | लिंक्ड सूची]] के रूप में अनुक्रम के स्पष्ट प्रतिनिधित्व के लिए, रूपांतरण करने के लिए n<sub>2/4</sub> संचालन के बारे में (विभिन्न कारणों से) दोनों की आवश्यकता होती है। n के छोटे होने की संभावना के साथ (विशेष रूप से यदि सभी क्रमपरिवर्तनों की पीढ़ी की आवश्यकता है) जो कि बहुत अधिक समस्या नहीं है, लेकिन यह पता चला है कि यादृच्छिक और व्यवस्थित पीढ़ी दोनों के लिए सरल विकल्प हैं जो काफी बेहतर करते हैं। इस कारण से यह उपयोगी प्रतीत नहीं होता है, चूंकि निश्चित रूप से संभव है, एक विशेष डेटा संरचना को नियोजित करने के लिए जो O(n log n) समय में लेह्मर कोड से क्रमचय में रूपांतरण करने की अनुमति देगा।
 ==== क्रमपरिवर्तन की यादृच्छिक पीढ़ी ====
 {{Main|फिशर–येट्स फेरबदल}}
-'''n मानों के दिए गए अनुक्रम के [[ यादृच्छिक क्रमपरिवर्तन | यादृच्छिक क्रमपरिवर्तन]] उत्पन्न करने के लिए, इससे कोई फर्क नहीं पड़ता है कि अनुक्रम में n का एक यादृच्छिक रूप से चयनित क्रमपरिवर्तन लागू किया जाए, या अनुक्रम के विशिष्ट (मल्टीसेट) क्रमपरिवर्तनों के सेट से एक यादृच्छिक तत्व का चयन किया जाए। ऐसा इसलिए है, क्योंकि दोहराए गए मानों के मामले में n के कई अलग-अलग क्रमपरिवर्तन हो सकते हैं, जिसके परिणामस्वरूप एक ही अनुमत अनुक्रम होता है, ऐसे क्रमपरिवर्तन की संख्या प्रत्येक संभावित परिणाम के लिए समान होती है। व्यवस्थित पीढ़ी के विपरीत, जो संख्या n की वृद्धि के कारण बड़े n के लिए अक्षम्य हो जाता है!, यह मानने का कोई कारण नहीं है कि यादृच्छिक पीढ़ी के लिए n छोटा होगा।'''
+एन मानों के दिए गए अनुक्रम के [[यादृच्छिक क्रमपरिवर्तन]] उत्पन्न करने के लिए, इससे कोई फ़र्क नहीं पड़ता कि कोई अनुक्रम में n का यादृच्छिक रूप से चयनित क्रमपरिवर्तन लागू करता है, या अनुक्रम के विशिष्ट (मल्टीसेट) क्रमपरिवर्तनों के सेट से एक यादृच्छिक तत्व चुनता है। ऐसा इसलिए है, क्योंकि दोहराए गए मानों के मामले में n के कई अलग-अलग क्रमपरिवर्तन हो सकते हैं, जिसके परिणामस्वरूप एक ही अनुमत अनुक्रम होता है, ऐसे क्रमपरिवर्तन की संख्या प्रत्येक संभावित परिणाम के लिए समान होती है। व्यवस्थित पीढ़ी के विपरीत, जो संख्या n की वृद्धि के कारण बड़े n के लिए अक्षम्य हो जाती है!  यह मानने का कोई कारण नहीं है कि यादृच्छिक पीढ़ी के लिए n छोटा होगा।
-एक यादृच्छिक क्रमचय उत्पन्न करने के लिए मूल विचार n! पूर्णांकों का क्रम d<sub>1</sub>,डी<sub>2</sub>,...,डी<sub>''n''</sub> संतुष्टि देने वाला {{math|0 ≤ ''d''<sub>''i''</sub> &lt; ''i''}} (चूंकि डी<sub>1</sub> हमेशा शून्य होता है इसे छोड़ा जा सकता है) और इसे एक विशेषण पत्राचार के माध्यम से क्रमचय में परिवर्तित करने के लिए। बाद के पत्राचार के लिए लेहमर कोड के रूप में (रिवर्स) अनुक्रम की व्याख्या की जा सकती है, और यह [[ रोनाल्ड फिशर ]] और [[ फ्रैंक येट्स ]] द्वारा पहली बार 1938 में प्रकाशित एक जनरेशन विधि देता है।<ref>{{cite book
+एक यादृच्छिक क्रमचय उत्पन्न करने के लिए मूल विचार n! पूर्णांकों के अनुक्रम d<sub>1</sub>,d<sub>2</sub>,..., d<sub>''n''</sub> संतोषजनक {{math|0 ≤ ''d''<sub>''i''</sub> &lt; ''i''}} (चूंकि d<sub>1</sub> हमेशा शून्य होता है इसे छोड़ा जा सकता है) और इसे एक विशेषण पत्राचार के माध्यम से क्रमचय में परिवर्तित करने के लिए। बाद के पत्राचार के लिए लेहमर कोड के रूप में (रिवर्स) अनुक्रम की व्याख्या की जा सकती है, और यह [[ रोनाल्ड फिशर |रोनाल्ड फिशर]] और [[ फ्रैंक येट्स | फ्रैंक येट्स]] द्वारा पहली बार 1938 में प्रकाशित एक जनरेशन विधि देता है।<ref>{{cite book
 |author1=Fisher, R.A. |author2=Yates, F. | title = जैविक, कृषि और चिकित्सा अनुसंधान के लिए सांख्यिकीय तालिकाएँ| orig-year = 1938
 | edition = 3rd
@@ Line 367: / Line 367: @@
 | location = London
 | oclc = 14222135
 }}</ref>
-जबकि उस समय कंप्यूटर कार्यान्वयन कोई समस्या नहीं थी, यह विधि लेह्मर कोड से क्रमचय में कुशलतापूर्वक परिवर्तित करने के लिए ऊपर स्केच की गई कठिनाई से ग्रस्त है। एक अलग विशेषण पत्राचार का उपयोग करके इसका उपचार किया जा सकता है: d का उपयोग करने के बाद<sub>''i''</sub> अनुक्रम के शेष तत्वों (i के घटते मूल्यों के लिए) के बीच एक तत्व का चयन करने के लिए, तत्व को हटाने और आगे के तत्वों को एक स्थान पर स्थानांतरित करके अनुक्रम को संकुचित करने के बजाय, अंतिम शेष तत्व के साथ एक [[ स्वैप (कंप्यूटर विज्ञान) ]] तत्व। इस प्रकार चयन के लिए शेष तत्व समय के प्रत्येक बिंदु पर एक क्रमागत श्रेणी बनाते हैं, भले ही वे मूल क्रम में उसी क्रम में न हों, जैसा कि उन्होंने किया था। पूर्णांकों के क्रम से क्रमपरिवर्तन तक का मानचित्रण कुछ जटिल है, लेकिन इसे तत्काल [[ प्रेरण (गणित) ]] द्वारा प्रत्येक क्रमपरिवर्तन को ठीक एक तरह से उत्पन्न करने के लिए देखा जा सकता है। जब चयनित तत्व अंतिम शेष तत्व होता है, तो स्वैप ऑपरेशन को छोड़ा जा सकता है। यह स्थिति के लिए परीक्षण की गारंटी देने के लिए पर्याप्त रूप से अक्सर नहीं होता है, लेकिन अंतिम तत्व को चयन के उम्मीदवारों के बीच शामिल किया जाना चाहिए, यह सुनिश्चित करने के लिए कि सभी क्रमपरिवर्तन उत्पन्न किए जा सकते हैं।
+जबकि उस समय कंप्यूटर कार्यान्वयन कोई समस्या नहीं थी, यह विधि लेह्मर कोड से क्रमचय में कुशलतापूर्वक परिवर्तित करने के लिए ऊपर स्केच की गई कठिनाई से ग्रस्त है। एक अलग विशेषण पत्राचार का उपयोग करके इसका उपचार किया जा सकता है: अनुक्रम के i शेष तत्वों (i के घटते मूल्यों के लिए) के बीच एक तत्व का चयन करने के लिए di का उपयोग करने के बाद, तत्व को हटाने और अनुक्रम को एक स्थान पर स्थानांतरित करके अनुक्रम को संकुचित करने के बजाय, अंतिम शेष तत्व के साथ तत्व को [[ स्वैप (कंप्यूटर विज्ञान) |स्वैप (कंप्यूटर विज्ञान)]] करता है। इस प्रकार चयन के लिए शेष तत्व समय के प्रत्येक बिंदु पर एक सतत श्रेणी बनाते हैं, भले ही वे उसी क्रम में न हों जैसा कि वे मूल अनुक्रम में थे। पूर्णांकों के अनुक्रम से क्रमचय तक की मैपिंग कुछ जटिल है, लेकिन यह देखा जा सकता है कि प्रत्येक क्रमचय को ठीक एक तरह से उत्पन्न किया जा सकता है, एक तत्काल [[ प्रेरण (गणित) |प्रेरण (गणित)]] द्वारा। जब चयनित तत्व अंतिम शेष तत्व होता है, तो स्वैप ऑपरेशन छोड़ा जा सकता है। हालत के लिए वारंट परीक्षण के लिए यह पर्याप्त रूप से अक्सर नहीं होता है, लेकिन अंतिम तत्व को चयन के उम्मीदवारों के बीच शामिल किया जाना चाहिए, यह गारंटी देने के लिए कि सभी क्रमपरिवर्तन उत्पन्न किए जा सकते हैं।
-का एक यादृच्छिक क्रमपरिवर्तन उत्पन्न करने के लिए परिणामी एल्गोरिथ्म <code>''a''[0], ''a''[1], ..., ''a''[''n'' − 1]</code> [[ स्यूडोकोड ]] में निम्नानुसार वर्णित किया जा सकता है:
+<code>''a''[0], ''a''[1], ..., ''a''[''n'' − 1]</code> का एक यादृच्छिक क्रमचय उत्पन्न करने के लिए परिणामी एल्गोरिथम को [[ स्यूडोकोड |स्यूडोकोड]] में निम्नानुसार वर्णित किया जा सकता है:
-  ''i'' के लिए ''n'' से downto 2 करना
+  '''for''' ''i'' '''from''' ''n'' '''downto''' 2 '''do'''
-      ''डी<sub>i</sub>← {0, ..., i − 1} का यादृच्छिक अवयव
+      ''d<sub>i</sub>'' ← random element of { 0, ..., ''i'' − 1 }
-     'स्वैप' ए [डी<sub>i</sub>] और एक[i - 1]
+     '''swap''' ''a''[''d<sub>i</sub>''] and ''a''[''i'' − 1]
 इसे सरणी के आरंभीकरण के साथ जोड़ा जा सकता है <code>''a''[''i''] = ''i''</code> निम्नलिखित नुसार
+ '''for''' ''i'' '''from''' 0 '''to''' ''n''−1 '''do'''
+     ''d<sub>i</sub>''<sub>+1</sub> ← random element of { 0, ..., ''i'' }
+     ''a''[''i''] ← ''a''[''d<sub>i</sub>''<sub>+1</sub>]
- ''i'' के लिए 0 से ''n''−1 do . तक
+     ''a''[''d<sub>i</sub>''<sub>+1</sub>] ← ''i''
-     ''डी''<sub>''i''+1</sub> ← यादृच्छिक अवयव {0, ..., i }
+अगर d<sub>''i''+1</sub> = i, पहला असाइनमेंट एक गैर-आरंभिक मान की नकल करेगा, लेकिन दूसरा इसे सही मान i के साथ अधिलेखित कर देगा।
-     एक [मैं] ← एक [डी<sub>''i''+1</sub>]
-     एक [डी<sub>''i''+1</sub>] ← मैं
-अगर डी<sub>''i''+1</sub> = i, पहला असाइनमेंट एक गैर-आरंभिक मान की नकल करेगा, लेकिन दूसरा इसे सही मान i के साथ अधिलेखित कर देगा।
-हालांकि, फिशर-येट्स क्रमपरिवर्तन उत्पन्न करने के लिए सबसे तेज़ एल्गोरिदम नहीं है, क्योंकि फिशर-येट्स अनिवार्य रूप से अनुक्रमिक एल्गोरिदम है और प्रक्रियाओं को विभाजित और जीत समानांतर में समान परिणाम प्राप्त कर सकते हैं।<ref>{{cite news|author1=Bacher, A. |author2=Bodini, O.|author3=Hwang, H.K.|author4=Tsai, T.H. | title = कॉइन टॉसिंग द्वारा यादृच्छिक क्रमपरिवर्तन उत्पन्न करना: शास्त्रीय एल्गोरिदम, नया विश्लेषण और आधुनिक कार्यान्वयन।| edition = ACM Trans. Algorithms 13(2): 24:1–24:43
+चूंकि, फिशर-येट्स क्रमचय उत्पन्न करने के लिए सबसे तेज़ एल्गोरिथम नहीं है, क्योंकि फिशर-येट्स अनिवार्य रूप से एक अनुक्रमिक एल्गोरिथम है और "फूट डालो और जीतो" प्रक्रियाएं समानांतर में समान परिणाम प्राप्त कर सकती हैं।<ref>{{cite news|author1=Bacher, A. |author2=Bodini, O.|author3=Hwang, H.K.|author4=Tsai, T.H. | title = कॉइन टॉसिंग द्वारा यादृच्छिक क्रमपरिवर्तन उत्पन्न करना: शास्त्रीय एल्गोरिदम, नया विश्लेषण और आधुनिक कार्यान्वयन।| edition = ACM Trans. Algorithms 13(2): 24:1–24:43
 | year = 2017
 | pages = 24–43
 }}</ref>
 ==== शब्दावली क्रम में पीढ़ी ====
-किसी दिए गए अनुक्रम के सभी क्रमपरिवर्तन को व्यवस्थित रूप से उत्पन्न करने के कई तरीके हैं।<ref name=sedegewick1977>{{cite journal
+किसी दिए गए अनुक्रम के सभी क्रमचयों को व्यवस्थित रूप से उत्पन्न करने के कई तरीके हैं।<ref name="sedegewick1977">{{cite journal
 |last=Sedgewick|first=R
 |title=क्रमपरिवर्तन पीढ़ी के तरीके|journal=Computing Surveys|year=1977|volume=9
@@ Line 400: / Line 398: @@
 |doi=10.1145/356689.356692
 |s2cid=12139332
-}}</ref>
+}}</ref> एक क्लासिक, सरल, और लचीला एल्गोरिदम [[ लेक्सिकोग्राफिक ऑर्डरिंग ]] में अगले क्रमचय को खोजने पर आधारित है, यदि यह मौजूद है। यह दोहराए गए मानों को संभाल सकता है, जिस स्थिति के लिए यह एक बार प्रत्येक विशिष्ट मल्टीसेट क्रमचय उत्पन्न करता है। यहां तक कि साधारण क्रमपरिवर्तन के लिए भी यह लेह्मर कोड के लिए कोशीय क्रम में मान उत्पन्न करने (संभवत: भाज्य संख्या प्रणाली का उपयोग करके) और उन्हें क्रमपरिवर्तन में परिवर्तित करने की तुलना में काफी अधिक कुशल है। यह अनुक्रम को (कमजोर) बढ़ते हुए क्रम में क्रमबद्ध करके शुरू होता है (जो इसके लेक्सिकोग्राफिक रूप से न्यूनतम क्रमपरिवर्तन देता है), और तब तक अगले क्रमचय के लिए आगे बढ़ना दोहराता है जब तक कि एक मिल जाता है। यह पद्धति 14वीं शताब्दी के भारत में [[ नारायणा पंडित | नारायणा पंडित]] के पास वापस चली जाती है, और इसे बार-बार फिर से खोजा गया है।{{sfn|Knuth|2005|pp=1–26}}
-एक क्लासिक, सरल और लचीला एल्गोरिथम [[ लेक्सिकोग्राफिक ऑर्डरिंग ]] में अगले क्रमपरिवर्तन को खोजने पर आधारित है, यदि यह मौजूद है। यह दोहराए गए मानों को संभाल सकता है, जिस स्थिति के लिए यह प्रत्येक विशिष्ट मल्टीसेट क्रमपरिवर्तन को एक बार उत्पन्न करता है। यहां तक कि सामान्य क्रमपरिवर्तन के लिए भी यह लेहमर कोड के लिए लेक्सिकोग्राफिक क्रम में मान उत्पन्न करने (संभवतः फैक्टोरियल नंबर सिस्टम का उपयोग करके) और उन्हें क्रमपरिवर्तन में परिवर्तित करने की तुलना में काफी अधिक कुशल है। यह अनुक्रम को (कमजोर रूप से) बढ़ते क्रम में क्रमबद्ध करके शुरू होता है (जो इसकी शब्दावली में न्यूनतम क्रमपरिवर्तन देता है), और तब तक अगले क्रमपरिवर्तन के लिए आगे बढ़ते हुए दोहराता है जब तक कि एक पाया जाता है। यह विधि 14वीं शताब्दी के भारत में [[ नारायणा पंडित ]]ा से मिलती है, और इसे बार-बार खोजा गया है।{{sfn|Knuth|2005|pp=1–26}}
-निम्नलिखित एल्गोरिथम किसी दिए गए क्रमपरिवर्तन के बाद अगले क्रमचय को लेक्सिकोग्राफिक रूप से उत्पन्न करता है। यह दिए गए क्रमपरिवर्तन को जगह-जगह बदल देता है।
+निम्नलिखित एल्गोरिथम दिए गए क्रमचय के बाद अगले क्रमचय को लेक्सिकोग्राफिक रूप से उत्पन्न करता है। यह दिए गए क्रमचय को यथास्थान बदल देता है।
-# सबसे बड़ा सूचकांक k इस प्रकार ज्ञात कीजिए कि {{nowrap|''a''[''k''] < ''a''[''k'' + 1]}}. यदि ऐसा कोई सूचकांक मौजूद नहीं है, तो क्रमचय अंतिम क्रमपरिवर्तन है।
+# सबसे बड़ा सूचकांक k ज्ञात कीजिए जैसे कि {{nowrap|''a''[''k''] < ''a''[''k'' + 1]}}। यदि ऐसा कोई सूचकांक मौजूद नहीं है, क्रमचय अंतिम क्रमचय है।
-# k से बड़ा सबसे बड़ा सूचकांक l इस प्रकार ज्ञात करें कि {{nowrap|''a''[''k''] < ''a''[''l'']}}.
+# k से बड़ा सबसे बड़ा सूचकांक l ज्ञात करें जैसे कि {{nowrap|''a''[''k''] < ''a''[''l'']}}।
-# a[k] के मान को a[l] के साथ स्वैप करें।
+# a[k] के मान को a[l] से बदलें।
-# ए [के + 1] से अनुक्रम को उलट दें और अंतिम तत्व ए [एन] को शामिल करें।
+# अनुक्रम को a[k + 1] से उलट दें और अंतिम तत्व a[n] को शामिल कर लें।
-उदाहरण के लिए, अनुक्रम [1, 2, 3, 4] (जो बढ़ते क्रम में है) दिया गया है, और यह देखते हुए कि सूचकांक शून्य-आधारित संख्या है|शून्य-आधारित, चरण इस प्रकार हैं:
+उदाहरण के लिए, दिया ग�