क्रमचय

For other uses, see क्रमचय (disambiguation).

"एनपीआर" redirects here. For other uses, see एनपीआर (बहुविकल्पी).

File:Permutations RGB.svg

छह पंक्तियों में से प्रत्येक तीन अलग-अलग गेंदों का एक अलग क्रमपरिवर्तन है

गणित में, एक सेट का क्रमचय, मोटे तौर पर, इसके सदस्यों की एक अनुक्रम या रैखिक क्रम में व्यवस्था है, या यदि सेट पहले से ही क्रमबद्ध है, तो इसके तत्वों की पुनर्व्यवस्था है।, या यदि समुच्चय पहले से ही क्रमबद्ध है, तो इसके तत्वों की पुनर्व्यवस्था है। शब्द "क्रमचय" भी आदेशित सेट के रैखिक क्रम को बदलने के कार्य या प्रक्रिया को संदर्भित करता है।।

क्रमपरिवर्तन संयोजनों से भिन्न होते हैं, जो क्रम की परवाह किए बिना एक सेट के कुछ सदस्यों के चयन होते हैं। उदाहरण के लिए, टुपल्स के रूप में लिखे गए सेट के छह क्रमपरिवर्तन हैं {1, 2, 3}, अर्थात् (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), और (3, 2, 1)। ये तीन-तत्वों के इस सेट के सभी संभावित क्रम हैं। जिन शब्दों के वर्ण भिन्न हैं उनके एनाग्राम भी क्रमचय हैं: अक्षरों को पहले से ही मूल शब्द में क्रमबद्ध किया गया है, और विपर्यय अक्षरों का पुनर्क्रमण है। साहचर्य और समूह सिद्धांत के क्षेत्र में परिमित सेट के क्रमपरिवर्तन का अध्ययन एक महत्वपूर्ण विषय है।

क्रमपरिवर्तन का उपयोग गणित की लगभग हर शाखा में और विज्ञान के कई अन्य क्षेत्रों में किया जाता है। कंप्यूटर विज्ञान में, उनका उपयोग सॉर्टिंग एल्गोरिदम के विश्लेषण के लिए किया जाता है; क्वांटम भौतिकी में, कणों की अवस्थाओं का वर्णन करने के लिए; और जीव विज्ञान में, आरएनए अनुक्रमों का वर्णन करने के लिए।

n विशिष्ट वस्तुओं के क्रमपरिवर्तन की संख्या n भाज्य है, जिसे सामान्यतः n! के रूप में लिखा जाता है। जिसका अर्थ है n से कम या उसके बराबर सभी धनात्मक पूर्णांकों का गुणनफल है।

तकनीकी रूप से, समुच्चय S के क्रमचय को S से स्वयं पर एक आक्षेप के रूप में परिभाषित किया जाता है। अर्थात्, यह S से S तक का एक कार्य है जिसके लिए प्रत्येक तत्व के प्रतिबिंब के मान के लिए ठीक एक बार होता है। यह S के तत्वों की पुनर्व्यवस्था से संबंधित है जिसमें प्रत्येक तत्व S को संगत f(s) द्वारा प्रतिस्थापित किया जाता है। उदाहरण के लिए, ऊपर बताए गए क्रमचय (3, 1, 2) को फ़ंक्शन $\alpha$ के रूप में परिभाषित किया गया है

$\alpha (1)=3,\quad \alpha (2)=1,\quad \alpha (3)=2$.

सेट के सभी क्रमपरिवर्तनों का संग्रह एक समूह (गणित) बनाता है जिसे सेट के सममित समूह कहा जाता है। समूह संचालन संरचना है (उत्तरदायी में दो दी गई व्यवस्थाओं का प्रदर्शन), जिसके परिणामस्वरूप एक और पुनर्व्यवस्था होती है। चूंकि क्रमपरिवर्तन के गुण सेट तत्वों की प्रकृति पर निर्भर नहीं करते हैं, यह अधिकांशतः सेट के क्रमपरिवर्तन होते हैं $\{1,2,\ldots ,n\}$ जिन्हें क्रमपरिवर्तन का अध्ययन करने के लिए माना जाता है।

प्राथमिक साहचर्य में, k-क्रमपरिवर्तन, या आंशिक क्रमपरिवर्तन, एक सेट से चुने गए k विशिष्ट तत्वों की क्रमबद्ध व्यवस्था है। जब k समुच्चय के आकार के बराबर होता है, तो ये समुच्चय के क्रमचय होते हैं।

File:Rubik's cube.svg

1974 में एर्नो रूबिक द्वारा आविष्कार की गई लोकप्रिय पहेली रूबिक क्यूब में, पहेली के प्रत्येक मोड़ सतह के रंगों का क्रमपरिवर्तन बनाता है।

इतिहास

चीन में चिंग(पिनयिन: यी जिंग) में 1000 ईसा पूर्व के रूप में हेक्साग्राम नामक क्रमपरिवर्तन का उपयोग किया गया था।

अरब गणितज्ञ अल-खलील इब्न अहमद अल-फ़राहिदी अल-खलील (717-786) और क्रिप्टोग्राफर ने क्रिप्टोग्राफ़िक संदेशों की पुस्तक लिखी। इसमें स्वरों के साथ और बिना सभी संभावित अरबी शब्दों को सूचीबद्ध करने के लिए क्रमचय और संयोजन का पहला उपयोग सम्मलित करना है।

n वस्तुओं के क्रमचय की संख्या निर्धारित करने का नियम भारतीय संस्कृति में लगभग 1150 AD के आसपास ज्ञात था। भारतीय गणितज्ञ भास्कर द्वितीय द्वारा लीलावती में एक मार्ग सम्मलित है जो इसका अनुवाद करता है:

अंकगणितीय श्रृंखला के गुणन का गुणनफल एकता से शुरू और बढ़ता है और स्थानों की संख्या तक जारी रहता है, विशिष्ट अंकों के साथ संख्या की भिन्नता होगी।

1677 में, फैबियन स्टैडमैन ने चेंजिंग रिंगिंग में घंटियों के क्रमपरिवर्तन की संख्या की व्याख्या करते हुए फैक्टोरियल्स का वर्णन किया। दो घंटियों से शुरू करते हुए: "पहले, दो को दो विधियों से भिन्न होने के लिए स्वीकार किया जाना चाहिए", जिसे वह 1 2 और 2 1 दिखा कर दिखाता है। इसके बाद वह बताते हैं कि तीन घंटियों के साथ "तीन में से तीन गुणा दो आंकड़े उत्पन्न होते हैं" जो फिर से सचित्र है। उनकी व्याख्या में सम्मलित है "3 को हटा दें, और 1.2 रहेगा; 2 को हटा दें, और 1.3 रहेगा; 1 को हटा दें, और 2.3 रहेगा"। फिर वह चार घंटियों की ओर बढ़ता है और यह दर्शाता है कि तीन के चार अलग-अलग सेट होंगे। प्रभावी रूप से, यह एक पुनरावर्ती प्रक्रिया है। वह "कास्टिंग अवे" पद्धति का उपयोग करते हुए पांच घंटियों के साथ आगे बढ़ता है और परिणामी 120 संयोजनों को सारणीबद्ध करता है। इस बिंदु पर वह हार मान लेता है और टिप्पणी करता है:

अब इन विधियों की प्रकृति ऐसी है कि एक संख्या में परिवर्तन सभी छोटी संख्याओं में परिवर्तन को समझ लेता है, ... इतना अधिक है कि एक संख्या पर परिवर्तनों का एक पूर्ण समूह सभी कम संख्याओं के पूर्ण अंकों को एक पूरे निकाय में एकजुट करके बनने लगता है;

स्टैडमैन क्रमपरिवर्तन के विचार को विस्तृत करता है; वह 20 के एक स्थिर से वर्णमाला के अक्षरों और घोड़ों के क्रमपरिवर्तन की संख्या पर विचार करता है।

पहला मामला जिसमें प्रतीत होता है कि असंबद्ध गणितीय प्रश्नों का क्रमपरिवर्तन की मदद से अध्ययन किया गया था, 1770 के आसपास हुआ था, जब जोसेफ लुइस लाग्रेंज ने बहुपद समीकरणों के अध्ययन में देखा किसी समीकरण के मूलों के क्रमचय के गुण इसे हल करने की संभावनाओं से संबंधित होते हैं। काम की इस पंक्ति का परिणाम अंततः एवरिस्ट गैलोइस के काम के माध्यम से हुआ, गैलोइस सिद्धांत में, जो मूलांकों द्वारा बहुपद समीकरणों (एक अज्ञात में) को हल करने के संबंध में क्या संभव है और क्या असंभव है, इसका पूरा विवरण देता है। आधुनिक गणित में, ऐसी कई समान स्थितियाँ हैं जिनमें किसी समस्या को समझने के लिए उससे संबंधित कुछ क्रमपरिवर्तनों का अध्ययन करने की आवश्यकता होती है।

दोहराव के बिना क्रमपरिवर्तन

क्रमचय का सबसे सरल उदाहरण पुनरावृत्ति के बिना क्रमचय है जहाँ हम n वस्तुओं को n स्थानों में व्यवस्थित करने के संभावित विधियों की संख्या पर विचार करते हैं। एक सेट में क्रमपरिवर्तन की संख्या को परिभाषित करने के लिए फैक्टोरियल का विशेष अनुप्रयोग होता है जिसमें पुनरावृत्ति सम्मलित नहीं होती है। संख्या "n!" पढ़ें, वास्तव में उन विधियों की संख्या है जिनसे हम n चीजों को एक नए क्रम में पुनर्व्यवस्थित कर सकते हैं। उदाहरण के लिए, यदि हमारे पास तीन फल हैं: एक संतरा, सेब और नाशपाती, तो हम उन्हें बताए गए क्रम में खा सकते हैं, या हम उन्हें बदल सकते हैं (उदाहरण के लिए, एक सेब, एक नाशपाती फिर एक संतरा)। तब क्रमचय की सही संख्या है $3!=1\cdot 2\cdot 3=6$ आइटमों की संख्या (n) बढ़ने पर यह संख्या बहुत बड़ी हो जाती है।

इसी प्रकार, n वस्तुओं से k वस्तुओं की व्यवस्था की संख्या को कभी-कभी आंशिक क्रमपरिवर्तन या k-क्रमपरिवर्तन कहा जाता है। इसे $nPk$ (जो "n क्रमचय k" पढ़ता है) के रूप में लिखा जा सकता है, और संख्या $n(n-1)\cdots (n-k+1)$ के बराबर है। $n(n-1)\cdots (n-k+1)$ (जिसे $n!/(n-k)!$). के रूप में भी लिखा जाता है)

परिभाषा

गणित के ग्रंथों में यह लोअरकेस ग्रीक अक्षरों का उपयोग करके क्रमचय को निरूपित करने के लिए प्रथागत है। सामान्यतः, या तो $\alpha$ और $\beta$ , या $\sigma ,\tau$ और $\pi$ उपयोग किया गया हैं।

क्रमचय को समुच्चय S से स्वयं पर आक्षेप के रूप में परिभाषित किया जा सकता है। n तत्वों के साथ एक सेट के सभी क्रमपरिवर्तन एक सममित समूह बनाते हैं, जिसे S के रूप में दर्शाया जाता है, जहां समूह संचालन कार्य रचना है। इस प्रकार दो क्रमपरिवर्तन के लिए, $\pi$ और $\sigma$ तथा समूह में $S_{n}$ चार स्वयंसिद्ध समूह हैं:

1. क्लोजर (गणित) : यदि $\pi$ तथा $\sigma$ में हैं $S_{n}$ तो ऐसा है $\pi \sigma .$ सहबद्धता: किन्हीं तीन क्रमपरिवर्तनों के लिए $\pi ,\sigma ,\tau \in S_{n}$, $(\pi \sigma )\tau =\pi (\sigma \tau ).$
2. पहचान तत्व : एक पहचान क्रमचय है, निरूपित $\operatorname {id}$ और द्वारा परिभाषित $\operatorname {id} (x)=x$ सभी के लिए $x\in S$. किसी के लिए $\sigma \in S_{n}$, $\operatorname {id} \sigma =\sigma \operatorname {id} =\sigma .$
3. व्युत्क्रमा तत्व : प्रत्येक क्रमचय के लिए $\pi \in S_{n}$, एक व्युत्क्रम क्रमचय सम्मलित है $\pi ^{-1}\in S_{n}$, जिससे $\pi \pi ^{-1}=\pi ^{-1}\pi =\operatorname {id} .$

सामान्यतः, दो क्रमपरिवर्तनों का संघटन क्रम विनिमेय नहीं होता है, अर्थात, $\pi \sigma \neq \sigma \pi .$

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

एक क्रमचय को एक या एक से अधिक असंयुक्त चक्रों में विघटित किया जा सकता है, अर्थात्, कक्षा (समूह सिद्धांत), जो कुछ तत्वों पर क्रमचय के अनुप्रयोग को बार-बार अनुरेखित करने पर मिलते हैं। उदाहरण के लिए, क्रमपरिवर्तन $\sigma$ द्वारा परिभाषित $\sigma (7)=7$ 1 चक्र है, $(\,7\,)$ जबकि क्रमपरिवर्तन $\pi$ द्वारा परिभाषित $\pi (2)=3$ तथा $\pi (3)=2$ एक 2-चक्र है $(\,2\,3\,)$ (वाक्यविन्यास के विवरण के लिए, देखें § Cycle notation नीचे)। सामान्यतः, k लंबाई का एक चक्र, जो k तत्वों से बना होता है, k-चक्र कहलाता है।

1-चक्र $(\,x\,)$ में एक तत्व को क्रमचय का निश्चित बिंदु (गणित) कहा जाता है। एक क्रमचय जिसमें कोई निश्चित बिंदु नहीं है, को विक्षिप्तता कहा जाता है। 2-चक्रों को स्थानान्तरण कहा जाता है; इस तरह के क्रमचय केवल दो तत्वों का आदान-प्रदान करते हैं, अन्य को स्थिर छोड़ देते हैं।

अंकन

चूँकि क्रमचय को तत्ववार लिखना, अर्थात्, टुकड़े के कार्यों के रूप में, बोझिल है, उन्हें अधिक जटिल रूप से प्रस्तुत करने के लिए कई संकेतन का आविष्कार किया गया है। साइकिल अंकन कई गणितज्ञों के लिए इसकी जटिलनेस और इस तथ्य के कारण एक लोकप्रिय विकल्प है कि यह एक क्रमचय की संरचना को पारदर्शी बनाता है। जब तक अन्यथा निर्दिष्ट नहीं किया जाता है, तब तक यह इस लेख में प्रयुक्त संकेतन है, लेकिन अन्य संकेतन अभी भी व्यापक रूप से उपयोग किए जाते हैं, विशेष रूप से अनुप्रयोग क्षेत्रों में।

दो-पंक्ति संकेतन

ऑगस्टिन-लुई कॉची के दो-पंक्ति संकेतन में, पहली पंक्ति में S के तत्वों को सूचीबद्ध करता है, और दूसरी पंक्ति में प्रत्येक के नीचे उसकी छवि को सूचीबद्ध करता है।

उदाहरण के लिए, समुच्चय S = {1, 2, 3, 4, 5} का एक विशेष क्रमचय इस प्रकार लिखा जा सकता है

$\sigma ={\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}};$

इसका अर्थ है कि संतुष्ट σ(1) = 2, σ(2) = 5, σ(3) = 4, σ(4) = 3, तथा σ(5) = 1 को संतुष्ट करता है। S के तत्व किसी भी क्रम में प्रकट हो सकते हैं पहली पंक्ति में। इस क्रमपरिवर्तन को इस प्रकार भी लिखा जा सकता है:

$\sigma ={\begin{pmatrix}3&2&5&1&4\\4&5&1&2&3\end{pmatrix}},$

या

$\sigma ={\begin{pmatrix}5&1&4&3&2\\1&2&3&4&5\end{pmatrix}}.$

एक-पंक्ति संकेतन

यदि S के तत्वों के लिए "प्राकृतिक" क्रम है, कहें $x_{1},x_{2},\ldots ,x_{n}$, तो कोई इसे दो-पंक्ति संकेतन की पहली पंक्ति के लिए उपयोग करता है:

$\sigma ={\begin{pmatrix}x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\sigma (x_{1})&\sigma (x_{2})&\sigma (x_{3})&\cdots &\sigma (x_{n})\end{pmatrix}}.$

इस धारणा के तहत, कोई पहली पंक्ति को छोड़ सकता है और क्रमचय को एक-पंक्ति संकेतन में लिख सकता है

$(\sigma (x_{1})\;\sigma (x_{2})\;\sigma (x_{3})\;\cdots \;\sigma (x_{n}))$,

अर्थात्, एस के तत्वों की एक व्यवस्थित व्यवस्था के रूप में। नीचे वर्णित चक्र संकेतन से एक-पंक्ति संकेतन को अलग करने के लिए सावधानी बरतनी चाहिए। गणित साहित्य में, चक्र संकेतन के लिए उनका उपयोग करते समय, एक-पंक्ति संकेतन के लिए कोष्ठकों को छोड़ना एक सामान्य उपयोग है। एक-पंक्ति संकेतन को क्रमपरिवर्तन का शब्द (गणित) निरूपण भी कहा जाता है। उपरोक्त उदाहरण तब 2 5 4 3 1 होगा क्योंकि पहली पंक्ति के लिए प्राकृतिक क्रम 1 2 3 4 5 माना जाएगा। (इन प्रविष्टियों को केवल तभी अलग करने के लिए अल्पविराम का उपयोग करना विशिष्ट है, जब कुछ में दो या दो से अधिक अंक हों।) यह फॉर्म अधिक जटिल है, और प्राथमिक साहचर्य और कंप्यूटर साइंस में आम है। यह उन अनुप्रयोगों में विशेष रूप से उपयोगी है जहां S के तत्वों या क्रमचय की तुलना बड़े या छोटे के रूप में की जानी है।

साइकिल अंकन

चक्र संकेतन सेट के तत्वों पर बार-बार क्रमचय लागू करने के प्रभाव का वर्णन करता है। यह क्रमचय को चक्रीय क्रमपरिवर्तन के उत्पाद के रूप में व्यक्त करता है; चूँकि अलग-अलग चक्र अलग-अलग होते हैं, इसे "विघटित चक्रों में अपघटन" कहा जाता है।

चक्र संकेतन में क्रमचय $\sigma$ को लिखने के लिए, एक निम्नानुसार आगे बढ़ता है:

1. एक ओपनिंग ब्रैकेट लिखें, फिर $S$ का एक मनमाना तत्व x चुनें और इसे लिखें: $(\,x$
2. फिर x की कक्षा का पता लगाएं; अर्थात, $\sigma$ : $(\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots$ के क्रमिक अनुप्रयोगों के तहत इसके मूल्यों को लिखें।
3. तब तक दोहराएं जब तक कि मान x पर वापस न आ जाए और x के अतिरिक्त समापन कोष्ठक लिखें: $(\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots \,)$
4. अब S के एक तत्व y के साथ जारी रखें, जिसे अभी तक लिखा नहीं गया है, और उसी तरह आगे बढ़ें: $(\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots \,)(\,y\,\ldots \,)$
5. S के सभी तत्वों को चक्रों में लिखे जाने तक दोहराएं।

तो क्रमचय 2 5 4 3 1 (एक-पंक्ति संकेतन में) चक्र अंकन में (125)(34) के रूप में लिखा जा सकता है।

जबकि सामान्य रूप से क्रमपरिवर्तन नहीं करते हैं, अलग-अलग चक्र करते हैं; उदाहरण के लिए,

$$(\,1\,2\,5\,)(\,3\,4\,)=(\,3\,4\,)(\,1\,2\,5\,).$$

इसके अतिरिक्त, अलग-अलग शुरुआती बिंदुओं को चुनकर, प्रत्येक चक्र को अलग-अलग विधियों से लिखा जा सकता है; उदाहरण के लिए,

$$(\,1\,2\,5\,)(\,3\,4\,)=(\,5\,1\,2\,)(\,3\,4\,)=(\,2\,5\,1\,)(\,4\,3\,).$$

एक दिए गए क्रमपरिवर्तन के अलग-अलग चक्रों को कई अलग-अलग विधियों से लिखने के लिए कोई भी इन समानताओं को जोड़ सकता है।

1-चक्रों को अधिकांशतः चक्र संकेतन से हटा दिया जाता है, बशर्ते संदर्भ स्पष्ट हो; एस में किसी भी तत्व एक्स के लिए किसी भी चक्र में दिखाई नहीं दे रहा है, कोई भी $\sigma (x)=x$ मानता है। पहचान क्रमचय, जिसमें केवल 1-चक्र होते हैं, को एकल 1-चक्र (x), संख्या 1, या आईडी द्वारा दर्शाया जा सकता है।

चक्र संकेतन की एक सुविधाजनक विशेषता यह है कि व्युत्क्रम क्रमचय का चक्र अंकन क्रमचय के चक्रों में तत्वों के क्रम को व्युत्क्रम कर दिया जाता है। उदाहरण के लिए,

$$[(\,1\,2\,5\,)(\,3\,4\,)]^{-1}=(\,5\,2\,1\,)(\,4\,3\,).$$

विहित चक्र संकेतन

कुछ संयोजी संदर्भों में चक्रों में तत्वों के लिए और (असंबद्ध) चक्रों के लिए एक निश्चित क्रम को ठीक करना उपयोगी होता है। मिक्लोस बोना निम्नलिखित ऑर्डरिंग विकल्पों को कैननिकल चक्र संकेतन कहते हैं:

• प्रत्येक चक्र में सबसे बड़ा तत्व पहले सूचीबद्ध होता है
• चक्रों को उनके पहले तत्व के बढ़ते क्रम में क्रमबद्ध किया जाता है

उदाहरण के लिए, (312)(54)(8)(976) विहित चक्र संकेतन में एक क्रमचय है। विहित चक्र संकेतन एक-चक्र को नहीं छोड़ता है।

रिचर्ड पी. स्टेनली प्रतिनिधित्व के समान विकल्प को क्रमचय का "मानक प्रतिनिधित्व" कहते हैं,और मार्टिन एग्नर इसी धारणा के लिए "मानक रूप" शब्द का प्रयोग करते हैं। सर्गेई किताएव भी "मानक रूप" शब्दावली का उपयोग करते हैं, लेकिन दोनों विकल्पों को व्युत्क्रम कर देते हैं; अर्थात्, प्रत्येक चक्र अपने सबसे छोटे तत्व को पहले सूचीबद्ध करता है और चक्रों को उनके सबसे कम अर्थात पहले तत्वों के घटते क्रम में क्रमबद्ध किया जाता है।

क्रमपरिवर्तन की संरचना

दो क्रमपरिवर्तनों की संरचना को निरूपित करने के दो तरीके हैं। $\sigma \cdot \pi$ वह फ़ंक्शन है जो सेट के किसी भी तत्व x को $\sigma (\pi (x))$ पर मैप करता है (\pi (x))}।

सबसे सही क्रमपरिवर्तन पहले तर्क पर लागू होता है,

क्योंकि फ़ंक्शन एप्लिकेशन जिस तरह से लिखा गया है। चूँकि फ़ंक्शन रचना साहचर्य है, इसलिए क्रमपरिवर्तन पर रचना संचालन है: $(\sigma \pi )\tau =\sigma (\pi \tau )$ इसलिए, दो से अधिक क्रमचयों के गुणनफल सामान्यतः व्यक्त समूहन में कोष्ठक जोड़े बिना लिखे जाते हैं; वे सामान्यतः रचना को इंगित करने के लिए बिना किसी बिंदु या अन्य चिह्न के भी लिखे जाते हैं। कुछ लेखक सबसे बाएं कारक को पहले अभिनय करना पसंद करते हैं, ,

लेकिन इसके लिए क्रमचय को उनके तर्क के दाईं ओर लिखा जाना चाहिए, अधिकांशतः एक प्रतिपादक के रूप में, जहाँ σ^x पर अभिनय करते हुए x^σ लिखा जाता है; तो उत्पाद को x^σ·π = (x^σ)^π द्वारा परिभाषित किया जाता है। हालाँकि यह क्रमपरिवर्तन को गुणा करने के लिए एक अलग नियम देता है; यह लेख उस परिभाषा का उपयोग करता है जहां सबसे सही क्रमचय पहले लागू किया जाता है।

क्रमपरिवर्तन शब्द के अन्य उपयोग

एक आदेशित व्यवस्था के रूप में क्रमचय की अवधारणा कई सामान्यीकरणों को स्वीकार करती है जो क्रमचय नहीं हैं, लेकिन साहित्य में क्रमपरिवर्तन कहा गया है।

k-क्रमपरिवर्तन n

शब्द क्रमचय का एक कमजोर अर्थ, कभी-कभी प्राथमिक साहचर्य ग्रंथों में उपयोग किया जाता है, उन क्रमबद्ध व्यवस्थाओं को निर्दिष्ट करता है जिसमें कोई तत्व एक से अधिक बार नहीं होता है, लेकिन किसी दिए गए सेट से सभी तत्वों का उपयोग करने की आवश्यकता के बिना। विशेष मामलों को छोड़कर ये क्रमपरिवर्तन नहीं हैं, बल्कि आदेशित व्यवस्था अवधारणा के प्राकृतिक सामान्यीकरण हैं। वास्तव में, इस प्रयोग में अधिकांशतः आकार n के दिए गए सेट से लिए गए तत्वों की एक निश्चित लंबाई k की व्यवस्था पर विचार करना सम्मलित होता है, दूसरे शब्दों में, n के ये k-क्रमपरिवर्तन एक n-सेट के k-तत्व उपसमुच्चय की अलग-अलग क्रमबद्ध व्यवस्थाएँ हैं (कभी-कभी इसे पुराने साहित्य में विविधता या व्यवस्था कहा जाता है)। इन वस्तुओं को आंशिक क्रमपरिवर्तन या पुनरावृत्ति के बिना अनुक्रम के रूप में भी जाना जाता है, ऐसे शब्द जो "क्रमपरिवर्तन" के दूसरे, अधिक सामान्य अर्थ के साथ भ्रम से बचते हैं। $n$ के ऐसे $k$-क्रमपरिवर्तनों की संख्या को $P_{k}^{n}$, $_{n}P_{k}$, $^{n}P_{k}$, $P_{n,k}$, या $P(n,k)$ और इसका मूल्य उत्पाद द्वारा दिया जाता है

$P(n,k)=\underbrace {n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)} _{k\ \mathrm {factors} }$,

जो 0 है जब k > n, और अन्यथा के बराबर है

${\frac {n!}{(n-k)!}}.$

गुणनफल अच्छी तरह परिभाषित है, बिना इस धारणा के कि $n$ एक गैर-ऋणात्मक पूर्णांक है, और साहचर्य के बाहर भी इसका महत्व है; इसे पॉचहैमर प्रतीक$(n)_{k}$ या $k$-वीं गिरती फैक्टोरियल पावर $n^{\underline {k}}$ के $n$रूप में जाना जाता है।

क्रमपरिवर्तन शब्द का यह प्रयोग शब्द संयोजन से निकटता से संबंधित है। n-सेट S का k-तत्व संयोजन, S का k-तत्व उपसमुच्चय है, जिनमें से तत्वों का आदेश नहीं दिया गया है। S के सभी k तत्व उपसमुच्चयों को लेकर और उनमें से प्रत्येक को हर संभव तरीके से व्यवस्थित करके, हम एस के सभी के-क्रमपरिवर्तन प्राप्त करते हैं। एक n-सेट, C(n,k) के k-संयोजनों की संख्या इसलिए है n के k-क्रमपरिवर्तन की संख्या से संबंधित:

$C(n,k)={\frac {P(n,k)}{P(k,k)}}={\frac {\tfrac {n!}{(n-k)!}}{\tfrac {k!}{0!}}}={\frac {n!}{(n-k)!\,k!}}.$

इन संख्याओं को द्विपद गुणांक के रूप में भी जाना जाता है और इन्हें ${\binom {n}{k}}$ द्वारा निरूपित किया जाता है .

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

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

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

File:Permutations with repetition.svg

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

यदि एम एक परिमित मल्टीसेट है, तो एक मल्टीसेट क्रमचय एम के तत्वों की एक क्रमबद्ध व्यवस्था है जिसमें प्रत्येक तत्व एम में इसकी बहुलता के बराबर बार-बार प्रकट होता है। कुछ दोहराए गए अक्षरों वाले शब्द का विपर्यय एक मल्टीसेट क्रमचय का एक उदाहरण है। यदि एम के तत्वों की बहुलता (किसी क्रम में ली गई) $m_{1}$, $m_{2}$, ..., $m_{l}$ और उनका योग (अर्थात्, M का आकार) n है, तो M के बहु-सेट क्रमपरिवर्तनों की संख्या बहुपद गुणांक द्वारा दी जाती है,

${n \choose m_{1},m_{2},\ldots ,m_{l}}={\frac {n!}{m_{1}!\,m_{2}!\,\cdots \,m_{l}!}}={\frac {\left(\sum _{i=1}^{l}{m_{i}}\right)!}{\prod _{i=1}^{l}{m_{i}!}}}.$

उदाहरण के लिए, मिसीसिपी शब्द के अलग-अलग विपर्यय की संख्या है:

${\frac {11!}{1!\,4!\,4!\,2!}}=34650$.

मल्टीसेट M का k-क्रमपरिवर्तन, M के तत्वों की लंबाई k का अनुक्रम है जिसमें प्रत्येक तत्व एम में अपनी बहुलता से कई गुना कम या उसके बराबर दिखाई देता है (एक तत्व की पुनरावृत्ति संख्या)।

परिपत्र क्रमपरिवर्तन

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

दो गोलाकार क्रमपरिवर्तन समतुल्य होते हैं यदि एक को दूसरे में घुमाया जा सकता है (अर्थात, तत्वों की सापेक्ष स्थिति को बदले बिना चक्रित किया जाता है)। चार अक्षरों पर निम्नलिखित चार वृत्तीय क्रमचय एक समान माने जाते हैं।

 1 4 2 3
 4 3 2 1 3 4 1 2
 2 3 1 4

परिपत्र व्यवस्था को वामावर्त पढ़ा जाना है, इसलिए निम्नलिखित दो समतुल्य नहीं हैं क्योंकि कोई भी घूर्णन एक को दूसरे पर नहीं ला सकता है।

 1 1
 4 3 3 4
 2 2

n तत्वों वाले समुच्चय S के वृत्तीय क्रमचयों की संख्या (n – 1)! है।

गुण

n विशिष्ट वस्तुओं के क्रमचय की संख्या n! है।

k असंयुक्त चक्रों के साथ n-क्रमपरिवर्तनों की संख्या पहले प्रकार की सांकेतिक स्टर्लिंग संख्या है, जिसे c(n, k) द्वारा निरूपित किया जाता है।

साइकिल का प्रकार

क्रमपरिवर्तन $\sigma$ के n तत्वों के विभाजन वाले सेट के चक्र (निश्चित बिंदुओं सहित); इसलिए इन चक्रों की लंबाई n का पूर्णांक विभाजन (संख्या सिद्धांत) बनाती है, जिसे $\sigma$ का चक्र प्रकार (या कभी-कभी चक्र संरचना या चक्र आकार) कहा जाता है। $\sigma$ के प्रत्येक निश्चित बिंदु के लिए चक्र प्रकार में एक "1" है, प्रत्येक स्थानान्तरण के लिए एक "2", इत्यादि। चक्र का प्रकार $\beta =(1\,2\,5\,)(\,3\,4\,)(6\,8\,)(\,7\,)$$(3,2,2,1).$ है, इसे अधिक संक्षिप्त रूप में [1¹2²3¹] के रूप में भी लिखा जा सकता है।

अधिक सटीक रूप से, सामान्य रूप है $[1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}]$, जहां $\alpha _{1},\ldots ,\alpha _{n}$ संबंधित लंबाई के चक्रों की संख्या हैं। किसी दिए गए चक्र प्रकार के क्रमचय की संख्या है

${\frac {n!}{1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}\alpha _{1}!\alpha _{2}!\dotsm \alpha _{n}!}}$.

संयुग्मन क्रमपरिवर्तन

सामान्यतः, चक्र संकेतन में लिखे गए रचना क्रमपरिवर्तन आसानी से वर्णित पैटर्न का अनुसरण नहीं करते हैं - रचना के चक्र रचना किए जाने वाले चक्रों से भिन्न हो सकते हैं। हालाँकि संयुग्मन वर्ग के क्रमपरिवर्तन के विशेष स्थिति में चक्र प्रकार संरक्षित है $\sigma$ दूसरे क्रमपरिवर्तन द्वारा $\pi$, जिसका अर्थ है उत्पाद बनाना $\pi \sigma \pi ^{-1}$. यहां, $\pi \sigma \pi ^{-1}$ का संयुग्म है $\sigma$ द्वारा $\pi$ और इसके चक्र अंकन के लिए चक्र अंकन लेकर प्राप्त किया जा सकता है $\sigma$ और आवेदन $\pi$ इसमें सभी प्रविष्टियों के लिए। यह इस प्रकार है कि दो क्रमपरिवर्तन ठीक उसी समय संयुग्मित होते हैं जब उनके पास एक ही चक्र प्रकार होता है।

क्रमचय क्रम

एक क्रमचय का क्रम $\sigma$ सबसे छोटा सकारात्मक पूर्णांक m है ताकि $\sigma ^{m}=\mathrm {id}$ { पहचान} }। यह इसके चक्रों की लंबाई का कम से कम सामान्य गुणक है। उदाहरण के लिए, $(\,1\,3\,2)(\,4\,5\,)$ $2\cdot 3=6$ है।

क्रमपरिवर्तन की समता

Main article: एक क्रमचय की समानता

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

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

$\operatorname {sgn} (\sigma \pi )=\operatorname {sgn} \sigma \cdot \operatorname {sgn} \pi .$

यह इस प्रकार है कि $\operatorname {sgn} \left(\sigma \sigma ^{-1}\right)=+1.$

मैट्रिक्स प्रतिनिधित्व

Main article: क्रमपरिवर्तन मैट्रिक्स

एक क्रमचय मैट्रिक्स एक वर्ग मैट्रिक्स | n × n मैट्रिक्स है जिसमें प्रत्येक स्तंभ और प्रत्येक पंक्ति में ठीक एक प्रविष्टि 1 है, और अन्य सभी प्रविष्टियाँ 0 हैं। कई अलग-अलग सम्मेलन हैं जिनका उपयोग क्रमचय मैट्रिक्स को एक क्रमपरिवर्तन के लिए निर्दिष्ट करने के लिए किया जा सकता है। {1, 2, ..., एन} का। एक प्राकृतिक दृष्टिकोण क्रमचय σ मैट्रिक्स से संबद्ध करना है $M_{\sigma }$ जिसकी (i, j) प्रविष्टि 1 है यदि i = σ(j) और अन्यथा 0 है। इस परिपाटी के दो आकर्षक गुण हैं: पहला, आव्यूहों और क्रमपरिवर्तनों का गुणनफल एक ही क्रम में है, अर्थात्, $M_{\sigma }M_{\pi }=M_{\sigma \circ \pi }$ सभी क्रमपरिवर्तन σ और π के लिए। दूसरा, अगर ${\bf {e}}_{i}$ मानक आधार का प्रतिनिधित्व करता है $n\times 1$ स्तंभ वेक्टर (1 के बराबर ith प्रविष्टि वाला वेक्टर और 0 के बराबर अन्य सभी प्रविष्टियाँ), फिर $M_{\sigma }{\bf {e}}_{i}={\bf {e}}_{\sigma (i)}$.

उदाहरण के लिए, इस परिपाटी के साथ, क्रमपरिवर्तन से जुड़ा मैट्रिक्स $\sigma (1,2,3)=(2,1,3)$ है ${\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}$ और क्रमपरिवर्तन से जुड़ा मैट्रिक्स $\pi (1,2,3)=(2,3,1)$ है ${\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}$. फिर क्रमपरिवर्तन की संरचना है $(\sigma \circ \pi )(1,2,3)=\sigma (2,3,1)=(1,3,2)$, और संबंधित मैट्रिक्स उत्पाद है

$$M_{(2,1,3)}M_{(2,3,1)}={\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}{\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}={\begin{pmatrix}1&0&0\\0&0&1\\0&1&0\end{pmatrix}}=M_{(1,3,2)}.$$

File:Symmetric group 3; Cayley table; matrices.svg

क्रमचय आव्यूहों के गुणन के संगत क्रमचयों की संरचना।

साहित्य में व्युत्क्रमा सम्मेलन खोजना भी आम है, जहां एक क्रमचय σ मैट्रिक्स $P_{\sigma }=(M_{\sigma })^{-1}=(M_{\sigma })^{T}$ जिसकी (i, j) प्रविष्टि 1 है यदि j = σ(i) और अन्यथा 0 है। इस परिपाटी में, क्रमचय आव्यूह, क्रमचय से विपरीत क्रम में गुणा करते हैं, अर्थात, $P_{\sigma }P_{\pi }=P_{\pi \circ \sigma }$ सभी क्रमपरिवर्तन σ और π के लिए। इस पत्राचार में, क्रमचय आव्यूह मानक $1\times n$ पंक्ति सदिशों $({\bf {e}}_{i})^{T}$ एक में $({\bf {e}}_{i})^{T}P_{\sigma }=({\bf {e}}_{\sigma (i)})^{T}$

दाईं ओर केली टेबल 3 तत्वों के क्रमपरिवर्तन के लिए इन आव्यूहों को दिखाता है।

पूरी तरह से ऑर्डर किए गए सेट के क्रमपरिवर्तन

कुछ अनुप्रयोगों में, अनुमत सेट के तत्वों की एक दूसरे के साथ तुलना की जाएगी। इसके लिए आवश्यक है कि समुच्चय S का कुल क्रम हो जिससे किन्हीं भी दो तत्वों की तुलना की जा सके। सेट {1, 2, ..., n} सामान्य "≤" संबंध द्वारा पूरी तरह से आदेशित है और इसलिए यह इन अनुप्रयोगों में सबसे अधिक बार उपयोग किया जाने वाला सेट है, लेकिन सामान्यतः, कोई भी पूरी तरह से ऑर्डर किया गया सेट करेगा। इन अनुप्रयोगों में, क्रमचय में पदों के बारे में बात करने के लिए क्रमपरिवर्तन के आदेशित व्यवस्था दृश्य की आवश्यकता होती है।

ऐसे कई गुण हैं जो सीधे S के कुल क्रम से संबंधित हैं।

आरोहण, अवरोहण, दौड़ और अधिकता

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

k आरोही के साथ n के क्रमपरिवर्तन की संख्या है (परिभाषा के अनुसार) यूलेरियन संख्या $\textstyle \left\langle {n \atop k}\right\rangle$; यह k अवरोही के साथ n के क्रमचय की संख्या भी है। चूंकि कुछ लेखक ऑयलेरियन संख्या $\textstyle \left\langle {n \atop k}\right\rangle$ को k के साथ क्रमपरिवर्तन की संख्या के रूप में परिभाषित करते हैं। आरोही रन, जो k − 1 अवरोही के अनुरूप है। क्रमचय σ1σ2...σn की अधिकता एक सूचकांक j है जैसे कि σ_j > j. यदि असमानता सख्त नहीं है (अर्थात, σ_j ≥ j), तो j को एक कमजोर अतिरेक कहा जाता है। k अधिकता वाले n-क्रमपरिवर्तन की संख्या k अवरोही के साथ n-क्रमपरिवर्तन की संख्या के साथ मेल खाती है।

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

एक-पंक्ति संकेतन और विहित चक्र संकेतन के बीच एक संबंध है। विहित चक्र अंकन में क्रमचय $(\,2\,)(\,3\,1\,)$ पर विचार करें; यदि हम केवल कोष्ठकों को हटा दें, तो हम एक-पंक्ति संकेतन में क्रमचय $231$ प्राप्त करते हैं। डोमिनिक फोटा की संक्रमण लेम्मा इस पत्राचार की प्रकृति को n-क्रमपरिवर्तन (स्वयं के लिए) के सेट पर एक आक्षेप के रूप में स्थापित करती है। रिचर्ड पी. स्टेनली इस पत्राचार को मौलिक आपत्ति कहते हैं।

चलो $f(p)=q$ कोष्ठक-मिटाने वाला परिवर्तन हो जो $q$ को एक-पंक्ति नोटेशन में लौटाता है $p$ विहित में चक्र अंकन। जैसा कि कहा गया है, $f$ सभी कोष्ठकों को हटाकर संचालित होता है। व्युत्क्रम परिवर्तन का संचालन, {$f^{-1}(q)=p$, जो एक-पंक्ति संकेतन में $q$ दिए जाने पर विहित चक्र संकेतन में $p$ लौटाता है, यह थोड़ा कम सहज है। $q=q_{1}q_{2}\cdots q_{n}$ का पहला चक्र p}p विहित चक्र संकेतन में $q_{1}$ से शुरू होना चाहिए। जब तक बाद के तत्व $q_{1}$ से छोटे हैं, हम $p$ के समान चक्र में हैं। $p$ का दूसरा चक्र सबसे छोटे इंडेक्स $j$ से शुरू होता है, जैसे कि $q_{j}>q_{1}$। दूसरे शब्दों में, $q_{j}$ अपने बायीं ओर की सभी चीज़ों से बड़ा है, इसलिए इसे बाएँ से दाएँ अधिकतम कहा जाता है। कैनोनिकल चक्र संकेतन में प्रत्येक चक्र बाएं से दाएं अधिकतम के साथ शुरू होता है।

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

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

$q=f(p)$	$p=f^{-1}(q)$
$\mathbf {123} =(\,1\,)(\,2\,)(\,3\,)$	$123=\mathbf {(\,1\,)(\,2\,)(\,3\,)}$
$\mathbf {132} =(\,1\,)(\,3\,2\,)$	$132=\mathbf {(\,1\,)(\,3\,2\,)}$
$\mathbf {213} =(\,2\,1\,)(\,3\,)$	$213=\mathbf {(\,2\,1\,)(\,3\,)}$
$\mathbf {231} =(\,3\,1\,2\,)$	$321=\mathbf {(\,2\,)(\,3\,1\,)}$
$\mathbf {312} =(\,3\,2\,1\,)$	$231=\mathbf {(\,3\,1\,2\,)}$
$\mathbf {321} =(\,2\,)(\,3\,1\,)$	$312=\mathbf {(\,3\,2\,1\,)}$

पहले परिणाम के रूप में, ठीक k बाएँ से दाएँ मैक्सिमा के साथ n-क्रमपरिवर्तन की संख्या भी पहली तरह की सांकेतिक स्टर्लिंग संख्या $c(n,k)$ के बराबर है, इसके अतिरिक्त, फोटा की मैपिंग k-कमजोर उत्कृष्टता के साथ n-क्रमपरिवर्तन लेती है, k − 1 आरोही के साथ n-क्रमपरिवर्तन करती है। उदाहरण के लिए, (2)(31) = 321 में दो कमजोर एक्सीडेंस हैं (इंडेक्स 1 और 2 पर), जबकि f(321) = 231 में एक एसेंट (इंडेक्स 1 पर; अर्थात 2 से 3 तक) है।

व्युत्क्रम

Main article: व्युत्क्रम (असतत गणित)

File:15-Puzzle.jpg

15 पहेली में वर्गों को आरोही क्रम में लाने का लक्ष्य है। प्रारंभिक स्थितियाँ जिनमें विषम संख्या में व्युत्क्रम हैं, को हल करना असंभव है।

क्रमपरिवर्तन σ का व्युत्क्रम पदों की एक जोड़ी (i, j) है जहां क्रमचय की प्रविष्टियां विपरीत क्रम में होती हैं: $\sigma _{i}>\sigma _{j}$ तो $i<j$ दो आसन्न स्थितियों पर एक व्युत्क्रम है। उदाहरण के लिए, क्रमपरिवर्तन σ = 23154 में तीन व्युत्क्रम हैं: (1, 3), (2, 3), और (4, 5), प्रविष्टियों के जोड़े के लिए (2, 1), (3, 1), और ( 5, 4)।

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

k व्युत्क्रम के साथ n के क्रमचय की संख्या एक महोनियन संख्या द्वारा व्यक्त की जाती है, यह उत्पाद के विस्तार में X^k का गुणांक है

$$\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),$$

जिसे q-फैक्टोरियल [n]q! . उत्पाद का विस्तार नेकलेस (साहचर्य) में दिखाई देता है।

माना $\sigma \in S_{n},i,j\in \{1,2,\dots ,n\}$ जैसे कि$i<j$ तथा $\sigma (i)>\sigma (j)$। इस स्थिति में, मान लें कि व्युत्क्रम $(i,j)$ $\sigma (i)-\sigma (j)$।

कोबायाशी (2011) ने गणना सूत्र को सिद्ध किया

$$\sum _{i<j,\sigma (i)>\sigma (j)}(\sigma (i)-\sigma (j))=|\{\tau \in S_{n}\mid \tau \leq \sigma ,\tau {\text{ is bigrassmannian}}\}$$

जहाँ $\leq$ सममित समूहों में ब्रुहट क्रम को दर्शाता है। यह वर्गीकृत आंशिक क्रम अधिकांशतः कॉक्सेटर समूहों के संदर्भ में प्रकट होता है।

कंप्यूटिंग में क्रमपरिवर्तन

क्रमचय क्रमचय

n चीज़ों के क्रमचयों को निरूपित करने का एक तरीका 0 ≤ N <n! के साथ एक पूर्णांक N है, बशर्ते संख्या और क्रमचय के निरूपण को क्रमबद्ध व्यवस्था (अनुक्रम) के रूप में परिवर्तित करने के लिए सुविधाजनक तरीके दिए गए हों। यह स्वैच्छिक क्रमपरिवर्तन का सबसे जटिल प्रतिनिधित्व देता है, और कंप्यूटिंग में विशेष रूप से आकर्षक होता है जब n इतना छोटा होता है कि N को एक मशीन शब्द में रखा जा सकता है; 32-बिट शब्दों के लिए इसका अर्थ है n ≤ 12, और 64-बिट शब्दों के लिए इसका अर्थ है n ≤ 20। रूपांतरण संख्याओं के अनुक्रम के मध्यवर्ती रूप के माध्यम से किया जा सकता है d_n, d_n−1, ..., d₂, d₁, जहाँ di एक गैर-ऋणात्मक पूर्णांक है जो i से कम है (कोई d₁ को छोड़ सकता है, क्योंकि यह हमेशा 0 होता है, लेकिन इसकी उपस्थिति बाद के रूपांतरण को क्रमचय में वर्णित करना आसान बनाती है)। इसके बाद पहला कदम क्रम संख्या प्रणाली में केवल N को व्यक्त करना है, जो सिर्फ एक विशेष मिश्रित मूलांक प्रतिनिधित्व है, जहां, n! से कम संख्याओं के लिए, उत्तरोत्तर अंकों (n − 1)!, (n − 2)!, ..., 2!, 1! के लिए आधार स्थानीय मान या गुणन कारक हैं। दूसरा चरण इस अनुक्रम को एक लेहमर कोड या (लगभग समतुल्य) एक व्युत्क्रम तालिका के रूप में व्याख्या करता है।

Rothe diagram for $\sigma =(6,3,8,1,4,9,7,2,5)$

σi i	1	2	3	4	5	6	7	8	9	Lehmer code
1	×	×	×	×	×	•				d9 = 5
2	×	×	•							d8 = 2
3	×	×		×	×		×	•		d7 = 5
4	•									d6 = 0
5		×		•						d5 = 1
6		×			×		×		•	d4 = 3
7		×			×		•			d3 = 2
8		•								d2 = 0
9					•					d1 = 0
Inversion table	3	6	1	2	4	0	2	0	0

क्रमचय σ के लिए लेह्मर कोड में, संख्या d_n पहले पद σ₁ के लिए किए गए चुनाव को दर्शाती है, संख्या d_n−1 सेट के शेष n − 1 तत्वों के बीच दूसरे पद σ₂ के लिए किए गए चुनाव का प्रतिनिधित्व करती है, और आगे भी। अधिक सटीक रूप से, प्रत्येक d_n+1−i शेष तत्वों की संख्या σ_i शब्द से सख्ती से कम देता है। चूंकि वे शेष तत्व कुछ बाद के शब्द σ_j के रूप में आने के लिए बाध्य हैं, अंक d_n+1−i व्युत्क्रमों (i, j) को छोटे सूचकांक के रूप में सम्मलित करता है (मानों की संख्या j जिसके लिए i < j और σ_i > σ_j)। σ के लिए व्युत्क्रम तालिका काफी समान है, लेकिन यहाँ d_n+1−k व्युत्क्रमों की संख्या की गणना करता है (i,j) जहाँ k = σ_j उल्टे क्रम में प्रदर्शित होने वाले दो मानों में से छोटे के रूप में होता है। दोनों एनकोडिंग को n by n 'रोथ डायग्राम' द्वारा देखा जा सकता है

(हेनरिक अगस्त रोथ के नाम पर) जिसमें बिंदु (i,σ_i) क्रमपरिवर्तन की प्रविष्टियों को चिह्नित करते हैं, और (i,σ_j) पर एक क्रॉस व्युत्क्रम (i,j) को चिह्नित करता है; व्युत्क्रम की परिभाषा के अनुसार एक क्रॉस किसी भी वर्ग में प्रकट होता है जो अपने कॉलम में बिंदु (j,σ_j) से पहले और इसकी पंक्ति में बिंदु (i,σ_i) दोनों से पहले आता है। लेहमर कोड क्रमिक पंक्तियों में क्रॉस की संख्या को सूचीबद्ध करता है, जबकि व्युत्क्रमा तालिका लगातार कॉलम में क्रॉस की संख्या सूचीबद्ध करती है; यह व्युत्क्रम क्रमचय के लिए लेहमर कोड है, और इसके विपरीत।

प्रभावी रूप से एक लेह्मर कोड d_n, d_n−1, ..., d₂, d₁ को क्रमित समुच्चय S के क्रमचय में परिवर्तित करने के लिए, कोई S के तत्वों की सूची बढ़ते हुए क्रम से शुरू कर सकता है, और i के लिए 1 से n सेट σi से बढ़ कर उस सूची में उस तत्व के लिए जो d_n+1−i अन्य से पहले है, और उस तत्व को सूची से हटा दें। एक व्युत्क्रम तालिका d_n, d_n−1, ..., d₂, d₁ को संगत क्रमचय में बदलने के लिए, प्रारंभिक रूप से खाली अनुक्रम में S के तत्वों को सबसे बड़े से सबसे छोटे तक सम्मिलित करते हुए कोई भी d₁ से d_n तक की संख्या को पार कर सकता है; व्युत्क्रम तालिका से संख्या d का उपयोग करते हुए चरण में, S से तत्व उस बिंदु पर अनुक्रम में डाला जाता है जहां यह पहले से सम्मलित d तत्वों से पहले होता है। वैकल्पिक रूप से कोई व्युत्क्रम तालिका से संख्या और एस के तत्वों को विपरीत क्रम में संसाधित कर सकता है, n खाली स्लॉट की एक पंक्ति से शुरू होता है, और प्रत्येक चरण में तत्व को S से खाली स्लॉट में रखें जो d अन्य खाली स्लॉट से पहले हो।

क्रमिक प्राकृतिक संख्याओं को भाज्य संख्या प्रणाली में परिवर्तित करने से उन अनुक्रमों को लेक्सिकोग्राफिक क्रम में उत्पन्न होता है (जैसा कि किसी भी मिश्रित मूलांक संख्या प्रणाली के स्थिति में होता है), और आगे उन्हें क्रमपरिवर्तन में परिवर्तित करने से लेक्सिकोग्राफिक ऑर्डरिंग बरकरार रहती है, बशर्ते लेहमर कोड व्याख्या का उपयोग किया जाता है (इनवर्जन टेबल का उपयोग करके, एक अलग ऑर्डरिंग मिलती है, जहां कोई अपनी प्रविष्टियों के स्थान 1 के अतिरिक्त उनकी पहली प्रविष्टियों के मान से क्रमचय की तुलना करके शुरू करता है)। फैक्टोरियल नंबर सिस्टम प्रतिनिधित्व में संख्याओं का योग क्रमचय के व्युत्क्रमों की संख्या देता है, और उस योग की समानता क्रमचय का हस्ताक्षर (क्रमपरिवर्तन) देता है। इसके अतिरिक्त, व्युत्क्रम तालिका में शून्यों की स्थिति क्रमचय के बाएँ से दाएँ उच्चिष्ठ का मान देती है (उदाहरण 6, 8, 9 में) जबकि लेह्मर कोड में शून्य की स्थिति दाएँ-से-बाएँ मिनिमा की स्थिति है (उदाहरण में स्थिति 4, 8, 9 मान 1, 2, 5); यह सभी क्रमपरिवर्तनों के बीच ऐसे एक्स्ट्रेमा के वितरण की गणना करने की अनुमति देता है। लेह्मर कोड d_n, d_n−1, ..., d₂, d₁ के साथ क्रमचय का आरोहण n − i होता है यदि और केवल यदि d_i ≥ d_i+1।

क्रमपरिवर्तन उत्पन्न करने के लिए एल्गोरिदम

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

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

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

Main article: फिशर–येट्स फेरबदल

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

एक यादृच्छिक क्रमचय उत्पन्न करने के लिए मूल विचार n! पूर्णांकों के अनुक्रम d₁,d₂,..., d_n संतोषजनक 0 ≤ d_i < i (चूंकि d₁ हमेशा शून्य होता है इसे छोड़ा जा सकता है) और इसे एक विशेषण पत्राचार के माध्यम से क्रमचय में परिवर्तित करने के लिए। बाद के पत्राचार के लिए लेहमर कोड के रूप में (रिवर्स) अनुक्रम की व्याख्या की जा सकती है, और यह रोनाल्ड फिशर और फ्रैंक येट्स द्वारा पहली बार 1938 में प्रकाशित एक जनरेशन विधि देता है।

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

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

for i from n downto 2 do
 di ← random element of { 0, ..., i − 1 }

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

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

for i from 0 to n−1 do
 di+1 ← random element of { 0, ..., i }
 a[i] ← a[di+1]

 a[di+1] ← i

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

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

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

किसी दिए गए अनुक्रम के सभी क्रमचयों को व्यवस्थित रूप से उत्पन्न करने के कई तरीके हैं। एक क्लासिक, सरल, और लचीला एल्गोरिदम लेक्सिकोग्राफिक ऑर्डरिंग में अगले क्रमचय को खोजने पर आधारित है, यदि यह सम्मलित है। यह दोहराए गए मानों को संभाल सकता है, जिस स्थिति के लिए यह एक बार प्रत्येक विशिष्ट मल्टीसेट क्रमचय उत्पन्न करता है। यहां तक ​​कि साधारण क्रमपरिवर्तन के लिए भी यह लेह्मर कोड के लिए कोशीय क्रम में मान उत्पन्न करने (संभवत: भाज्य संख्या प्रणाली का उपयोग करके) और उन्हें क्रमपरिवर्तन में परिवर्तित करने की तुलना में काफी अधिक कुशल है। यह अनुक्रम को (कमजोर) बढ़ते हुए क्रम में क्रमबद्ध करके शुरू होता है (जो इसके लेक्सिकोग्राफिक रूप से न्यूनतम क्रमपरिवर्तन देता है), और तब तक अगले क्रमचय के लिए आगे बढ़ना दोहराता है जब तक कि एक मिल जाता है। यह पद्धति 14वीं शताब्दी के भारत में नारायणा पंडित के पास वापस चली जाती है, और इसे बार-बार फिर से खोजा गया है।

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

1. सबसे बड़ा सूचकांक k ज्ञात कीजिए जैसे कि a[k] < a[k + 1]। यदि ऐसा कोई सूचकांक सम्मलित नहीं है, क्रमचय अंतिम क्रमचय है।
2. k से बड़ा सबसे बड़ा सूचकांक l ज्ञात करें जैसे कि a[k] < a[l]।
3. a[k] के मान को a[l] से बदलें।
4. अनुक्रम को a[k + 1] से व्युत्क्रम दें और अंतिम तत्व a[n] को सम्मलित कर लें।

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

1. इंडेक्स k = 2, क्योंकि 3 को इंडेक्स पर रखा गया है यह सबसे बड़ा सूचकांक होने की शर्त को पूरा करता है जो अभी भी a[k + 1] से कम है जो कि 4 है।
2. अनुक्रमणिका l = 3, क्योंकि अनुक्रम में 4 ही एकमात्र मान है जो शर्त a[k] <a[l] को संतुष्ट करने के लिए 3 से अधिक है।
3. एक [2] और एक [3] के मूल्यों को नए अनुक्रम [1, 2, 4, 3] बनाने के लिए स्वैप किया जाता है।
4. k-इंडेक्स a [2] के बाद अंतिम तत्व के अनुक्रम को व्युत्क्रम दिया गया है। क्योंकि इस सूचकांक (3) के बाद केवल एक मान है, इस उदाहरण में क्रम अपरिवर्तित रहता है। इस प्रकार प्रारंभिक अवस्था के लेक्सिकोग्राफिक उत्तरदायीी की अनुमति है: [1, 2, 4, 3]।

इस एल्गोरिथम के बाद, अगला लेक्सिकोग्राफिक क्रमचय होगा [1, 3, 2, 4], और 24वाँ क्रमचय [4, 3, 2, 1] होगा जिस बिंदु पर a[k] <a[k + 1] सम्मलित नहीं है, यह दर्शाता है कि यह अंतिम क्रमचय है।

यह विधि लगभग 3 तुलनाओं और 1.5 स्वैप प्रति क्रमचय का उपयोग करती है, प्रारंभिक क्रम की गिनती नहीं करते हुए पूरे अनुक्रम में परिशोधित की जाती है।

न्यूनतम परिवर्तन के साथ पीढ़ी

Main articles: स्टाइनहॉस-जॉनसन-ट्रॉटर एल्गोरिथम and ढेर का एल्गोरिथ्म

उपरोक्त एल्गोरिथम का एक विकल्प, स्टाइनहॉस जॉनसन ट्रॉटर एल्गोरिथम, संपत्ति के साथ दिए गए अनुक्रम के सभी क्रमपरिवर्तनों पर एक आदेश उत्पन्न करता है कि इसके आउटपुट में कोई भी लगातार क्रमपरिवर्तन दो आसन्न मूल्यों की अदला-बदली से भिन्न होता है। क्रमपरिवर्तन पर यह आदेश 17 वीं शताब्दी के अंग्रेजी घंटी बजने वालों के लिए जाना जाता था, जिनके बीच इसे "सादे परिवर्तन" के रूप में जाना जाता था। इस पद्धति का एक लाभ यह है कि एक क्रमचय से दूसरे में परिवर्तन की छोटी मात्रा विधि को प्रति क्रमपरिवर्तन निरंतर समय में लागू करने की अनुमति देती है। वही आसानी से सम क्रमपरिवर्तन का सबसेट भी उत्पन्न कर सकता है, फिर से हर दूसरे आउटपुट क्रमपरिवर्तन को छोड़ कर निरंतर समय प्रति क्रमपरिवर्तन में।

स्टाइनहॉस-जॉनसन-ट्रॉटर का एक विकल्प हीप का एल्गोरिथम है जिसे 1977 में रॉबर्ट सेडगेविक (कंप्यूटर वैज्ञानिक) ने अनुप्रयोगों में क्रमपरिवर्तन उत्पन्न करने का सबसे तेज़ एल्गोरिथम कहा था।

निम्नलिखित आंकड़ा लंबाई $n=4$, और साहित्य में वर्णित छह अतिरिक्त एल्गोरिदम के सभी क्रमपरिवर्तन उत्पन्न करने के लिए उपरोक्त तीनों एल्गोरिदम का आउटपुट दिखाता है।

File:Permutation generation algorithms.svg

लंबाई के सभी क्रमपरिवर्तन का क्रम $n=4$ विभिन्न एल्गोरिदम द्वारा उत्पन्न। क्रमपरिवर्तन रंग-कोडित हैं, जहां   1,   2,   3,   4.

1. लेक्सिकोग्राफिक ऑर्डरिंग;
2. स्टाइनहॉस-जॉनसन-ट्रॉटर एल्गोरिथम;
3. हीप का एल्गोरिदम;
4. एर्लिच का स्टार-ट्रांसपोज़िशन एल्गोरिथम: प्रत्येक चरण में, क्रमपरिवर्तन की पहली प्रविष्टि बाद की प्रविष्टि के साथ बदली जाती है;
5. ज़क्स 'उपसर्ग उत्क्रमण एल्गोरिथम: प्रत्येक चरण में, वर्तमान क्रमपरिवर्तन के उपसर्ग को अगला क्रमपरिवर्तन प्राप्त करने के लिए व्युत्क्रम दिया जाता है;
6. सवादा-विलियम्स एल्गोरिथम: प्रत्येक क्रमचय पिछले एक से भिन्न होता है या तो चक्रीय लेफ्ट-शिफ्ट द्वारा एक स्थिति, या पहली दो प्रविष्टियों के आदान-प्रदान से भिन्न होता है;
7. कॉर्बेट का एल्गोरिथम: प्रत्येक क्रमचय पिछले एक से कुछ उपसर्ग के चक्रीय बाएं-शिफ्ट द्वारा एक स्थिति से भिन्न होता है;
8. सिंगल-ट्रैक ऑर्डरिंग: प्रत्येक स्तंभ अन्य स्तंभों का चक्रीय बदलाव है;
9. सिंगल-ट्रैक ग्रे कोड:प्रत्येक स्तंभ अन्य स्तंभों का एक चक्रीय बदलाव है, साथ ही कोई भी लगातार क्रमपरिवर्तन केवल एक या दो परिवर्तनों में भिन्न होता है।

मीनड्रिक क्रमपरिवर्तन

विसर्प (गणित) (मींड्रिक) प्रणालियां माध्य क्रमपरिवर्तन को जन्म देती हैं, वैकल्पिक क्रमपरिवर्तन का एक विशेष उपसमुच्चय। सेट {1, 2, ..., 2n} का एक वैकल्पिक क्रमचय एक चक्रीय क्रमपरिवर्तन है (बिना किसी निश्चित बिंदु के) जैसे कि चक्रीय अंकन में अंक विषम और सम पूर्णांकों के बीच वैकल्पिक होते हैं। मीनड्रिक क्रमपरिवर्तन आरएनए माध्यमिक संरचना के विश्लेषण में उपयोगी होते हैं। सभी वैकल्पिक क्रमपरिवर्तन मध्यम नहीं हैं। हीप के एल्गोरिथ्म के एक संशोधन का उपयोग सभी (2n) उत्पन्न किए बिना ऑर्डर n (अर्थात, लंबाई 2n) के सभी वैकल्पिक क्रमपरिवर्तन उत्पन्न करने के लिए किया गया है! क्रमपरिवर्तन। इन वैकल्पिक क्रमपरिवर्तनों की उत्पत्ति की आवश्यकता है, इससे पहले कि वे यह निर्धारित करने के लिए विश्लेषण करें कि वे मध्यम हैं या नहीं।

एल्गोरिथ्म पुनरावर्ती है। निम्न तालिका प्रक्रिया में एक चरण प्रदर्शित करती है। पिछले चरण में, लंबाई 5 के सभी वैकल्पिक क्रमपरिवर्तन उत्पन्न किए गए हैं। इनमें से प्रत्येक की तीन प्रतियों में दाहिनी ओर "6" जोड़ा गया है, और फिर इस अंतिम प्रविष्टि और एक समान स्थिति में पिछली प्रविष्टि को सम्मलित करते हुए एक अलग स्थानांतरण लागू किया जाता है (पहचान सहित; अर्थात कोई पारदर्शिता नहीं)।

पिछला सेट	अंकों का स्थानान्तरण	वैकल्पिक क्रमपरिवर्तन
1-2-3-4-5-6		1-2-3-4-5-6
	4, 6	1-2-3-6-5-4
	2, 6	1-6-3-4-5-2
1-2-5-4-3-6		1-2-5-4-3-6
	4, 6	1-2-5-6-3-4
	2, 6	1-6-5-4-3-2
1-4-3-2-5-6		1-4-3-2-5-6
	2, 6	1-4-3-6-5-2
	4, 6	1-6-3-2-5-4
1-4-5-2-3-6		1-4-5-2-3-6
	2, 6	1-4-5-6-3-2
	4, 6	1-6-5-2-3-4

अनुप्रयोग

त्रुटि का पता लगाने और सुधार एल्गोरिदम के इंटरलीवर घटक में क्रमपरिवर्तन का उपयोग किया जाता है, जैसे टर्बो कोड , उदाहरण के लिए 3GPP लॉन्ग टर्म इवोल्यूशन मोबाइल दूरसंचार मानक इन विचारों का उपयोग करता है (देखें 3GPP तकनीकी विनिर्देश 36.212[58])। इस तरह के अनुप्रयोग कुछ वांछनीय गुणों को संतुष्ट करने वाले क्रमपरिवर्तन के तेजी से उत्पादन का प्रश्न उठाते हैं। विधियों में से एक क्रमचय बहुपद पर आधारित है। अद्वितीय क्रमचय हैशिंग में इष्टतम हैशिंग के लिए एक आधार के रूप में भी।

यह भी देखें

• वैकल्पिक क्रमपरिवर्तन
• कनवल्शन
• चक्रीय क्रम
• सम और विषम क्रमपरिवर्तन
• जोसेफस क्रमपरिवर्तन
• लेवी-सिविटा प्रतीक
• क्रमपरिवर्तन विषयों की सूची
• प्रमुख सूचकांक
• क्रमपरिवर्तन श्रेणी
• क्रमपरिवर्तन समूह
• क्रमपरिवर्तन पैटर्न
• क्रमपरिवर्तन प्रतिनिधित्व (सममित समूह)
• संभावना
• डेटिंग नंबर
• छँटाई नेटवर्क
• प्रतिस्थापन सिफर
• सुपरपैटर्न
• सुपरपरम्यूटेशन
• बारह गुना रास्ता
• क्रमपरिवर्तन का कमजोर क्रम

ग्रन्थसूची

• Bogart, Kenneth P. (1990), Introductory Combinatorics (2nd ed.), Harcourt Brace Jovanovich, ISBN 978-0-15-541576-8
• Bóna, Miklós (2004), Combinatorics of Permutations, Chapman Hall-CRC, ISBN 978-1-58488-434-7
• Bona, Miklos (2012), Combinatorics of Permutations (2nd ed.), CRC Press, ISBN 978-1-4398-5051-0
• Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, ISBN 978-0-13-602040-0
• Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, ISBN 978-0-521-45761-3
• Carmichael, Robert D. (1956) [1937], Introduction to the theory of Groups of Finite Order, Dover, ISBN 978-0-486-60300-1
• Fraleigh, John B. (1976), A First Course In Abstract Algebra (2nd ed.), Reading: Addison-Wesley, ISBN 0-201-01984-1
• Gerstein, Larry J. (1987), Discrete Mathematics and Algebraic Structures, W.H. Freeman and Co., ISBN 978-0-7167-1804-8
• Hall, Marshall Jr. (1959), The Theory of Groups, MacMillan
• Humphreys, J. F. (1996), A course in group theory, Oxford University Press, ISBN 978-0-19-853459-4
• Knuth, Donald (1973), Sorting and Searching, The Art of Computer Programming, vol. 3 This book mentions the Lehmer code (without using that name) as a variant C₁,...,C_n of inversion tables in exercise 5.1.1–7 (p. 19), together with two other variants.
• Knuth, Donald (2005), Generating All Tuples and Permutations, The Art of Computer Programming, vol. 4, Addison–Wesley, ISBN 978-0-201-85393-3 Fascicle 2, first printing.
• McCoy, Neal H. (1968), Introduction To Modern Algebra, Revised Edition, Boston: Allyn and Bacon, LCCN 68015225
• Nering, Evar D. (1970), Linear Algebra and Matrix Theory (2nd ed.), New York: Wiley, LCCN 76091646
• Rotman, Joseph J. (2002), Advanced Modern Algebra, Prentice-Hall, ISBN 978-0-13-087868-7
• Stedman, Fabian (1677), Campanalogia, London The publisher is given as "W.S." who may have been William Smith, possibly acting as agent for the Society of College Youths, to which society the "Dedicatory" is addressed. In quotations the original long "S" has been replaced by a modern short "s".
• Webster's Seventh New Collegiate Dictionary, Springfield: G. & C. Merriam Company, 1969

अग्रिम पठन

• Biggs, Norman L. (2002), Discrete Mathematics (2nd ed.), Oxford University Press, ISBN 978-0-19-850717-8
• Foata, Dominique; Schutzenberger, Marcel-Paul (1970), Théorie Géométrique des Polynômes Eulériens, Lecture Notes in Mathematics, vol. 138, Berlin, Heidelberg: Springer-Verlag, ISBN 978-3-540-04927-2. The link is to a freely available retyped (LaTeX'ed) and revised version of the text originally published by Springer-Verlag.
• Knuth, Donald (1998), Sorting and Searching, The Art of Computer Programming, vol. 3 (Second ed.), Addison–Wesley, ISBN 978-0-201-89685-5. Section 5.1: Combinatorial Properties of Permutations, pp. 11–72.
• Sedgewick, Robert (1977). "Permutation generation methods". ACM Computing Surveys. 9 (2): 137–164. doi:10.1145/356689.356692. S2CID 12139332.
• Masato, Kobayashi (2011). "Enumeration of bigrassmannian permutations below a permutation in Bruhat order". Order. 1: 131–137.

बाहरी संबंध

• "Permutation", Encyclopedia of Mathematics, EMS Press, 2001 [1994]