क्रमचय

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

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

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

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

क्रमपरिवर्तन संयोजनों से भिन्न होते हैं, जो क्रम की परवाह किए बिना एक सेट के कुछ सदस्यों के चयन होते हैं। उदाहरण के लिए, टुपल्स के रूप में लिखे गए सेट के छह क्रमपरिवर्तन हैं {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 समुच्चय के आकार के बराबर होता है, तो ये समुच्चय के क्रमचय होते हैं।

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

इतिहास

चीन में I चिंग (पिनयिन: यी जिंग) में 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 फैक्टोरियल" पढ़ें, वास्तव में उन तरीकों की संख्या है जिनसे हम n चीजों को एक नए क्रम में पुनर्व्यवस्थित कर सकते हैं। उदाहरण के लिए, यदि हमारे पास तीन फल हैं: एक संतरा, सेब और नाशपाती, तो हम उन्हें बताए गए क्रम में खा सकते हैं, या हम उन्हें बदल सकते हैं (उदाहरण के लिए, एक सेब, एक नाशपाती फिर एक संतरा)। तब क्रमचय की सही संख्या है $3!=1\cdot 2\cdot 3=6$ आइटमों की संख्या (n) बढ़ने पर यह संख्या बहुत बड़ी हो जाती है।

इसी प्रकार, n वस्तुओं से k वस्तुओं की व्यवस्था की संख्या को कभी-कभी आंशिक क्रमपरिवर्तन या k-क्रमपरिवर्तन कहा जाता है। इसे $nPk$ (जो "n permute 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-टपल में कितनी बार प्रकट हो सकता है, इस पर कोई प्रतिबंध नहीं है, लेकिन यदि कोई तत्व कितनी बार दिखाई दे सकता है, इस पर प्रतिबंध लगाया जाता है, तो यह सूत्र अब मान्य नहीं है।

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

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

यदि एम एक परिमित मल्टीसेट है, तो एक मल्टीसेट क्रमचय एम के तत्वों की एक क्रमबद्ध व्यवस्था है जिसमें प्रत्येक तत्व एम में इसकी बहुलता के बराबर बार-बार प्रकट होता है। कुछ दोहराए गए अक्षरों वाले शब्द का विपर्यय एक मल्टीसेट क्रमचय का एक उदाहरण है। यदि एम के तत्वों की बहुलता (किसी क्रम में ली गई) $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)}.$$

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

साहित्य में उलटा सम्मेलन खोजना भी आम है, जहां एक क्रमचय σ मैट्रिक्स $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$ सही\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 अपने दाहिनी ओर शेष सभी तत्वों से बड़ा है, इसलिए अंतिम चक्र है {\displaystyle (\,9\,7\,6\,)}{\displaystyle (\,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: व्युत्क्रम (असतत गणित)

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 के क्रमचय की संख्या एक Mahonian संख्या द्वारा व्यक्त की जाती है, यह उत्पाद के विस्तार में 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 छोटा होगा।

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

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

i के लिए n से downto 2 करना
    डीi← {0, ..., i − 1} का यादृच्छिक अवयव
    'स्वैप' ए [डीi] और एक[i - 1]

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

i के लिए 0 से n−1 do . तक
    डीi+1 ← यादृच्छिक अवयव {0, ..., i }
    एक [मैं] ← एक [डीi+1]
    एक [डीi+1] ← मैं

अगर डी_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. ए [के + 1] से अनुक्रम को उलट दें और अंतिम तत्व ए [एन] को शामिल करें।

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

1. इंडेक्स k = 2, क्योंकि 3 को एक ऐसे इंडेक्स पर रखा गया है जो सबसे बड़ा इंडेक्स होने की शर्त को पूरा करता है जो अभी भी एक [k + 1] से कम है जो कि 4 है।
2. अनुक्रमणिका l = 3, क्योंकि 4 ही अनुक्रम में एकमात्र मान है जो a[k] <a[l] की स्थिति को संतुष्ट करने के लिए 3 से अधिक है।
3. नए अनुक्रम [1, 2, 4, 3] बनाने के लिए a[2] और a[3] के मानों की अदला-बदली की जाती है।
4. k-index 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: Steinhaus–Johnson–Trotter algorithm and Heap's algorithm

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

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

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

# लेक्सिकोग्राफिक ऑर्डरिंग;

1. स्टाइनहॉस-जॉनसन-ट्रॉटर एल्गोरिथम;
2. हीप का एल्गोरिदम;
3. एर्लिच का स्टार-ट्रांसपोज़िशन एल्गोरिथम: प्रत्येक चरण में, क्रमपरिवर्तन की पहली प्रविष्टि बाद की प्रविष्टि के साथ बदली जाती है;
4. Zaks 'उपसर्ग उत्क्रमण एल्गोरिथम: प्रत्येक चरण में, वर्तमान क्रमपरिवर्तन के उपसर्ग को अगला क्रमपरिवर्तन प्राप्त करने के लिए उलट दिया जाता है;
5. सवादा-विलियम्स एल्गोरिथम: रेफरी>Sawada, Joe; Williams, Aaron (2018). "सिग्मा-ताऊ समस्या के लिए एक हैमिल्टन पथ". Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. New Orleans, Louisiana: Society for Industrial and Applied Mathematics (SIAM). pp. 568–575. doi:10.1137/1.9781611975031.37.</ref> प्रत्येक क्रमचय पिछले एक से भिन्न होता है या तो चक्रीय लेफ्ट-शिफ्ट द्वारा एक स्थिति, या पहली दो प्रविष्टियों के आदान-प्रदान से भिन्न होता है;
6. कॉर्बेट का एल्गोरिथम: प्रत्येक क्रमचय पिछले एक से कुछ उपसर्ग के चक्रीय बाएं-शिफ्ट द्वारा एक स्थिति से भिन्न होता है;
7. सिंगल-ट्रैक ऑर्डरिंग: प्रत्येक स्तंभ अन्य स्तंभों का चक्रीय बदलाव है;
8. सिंगल-ट्रैक ग्रे कोड:प्रत्येक स्तंभ अन्य स्तंभों का एक चक्रीय बदलाव है, साथ ही कोई भी लगातार क्रमपरिवर्तन केवल एक या दो परिवर्तनों में भिन्न होता है।

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

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

Previous sets	Transposition of digits	Alternate permutations
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 देखें)

यह भी देखें

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

ग्रन्थसूची

• 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]