क्रमचय

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_{n}$, जहां समूह संचालन कार्यों की संरचना है। इस प्रकार दो क्रमपरिवर्तन के लिए, $\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-चक्रों को ट्रांसपोजिशन (गणित) कहा जाता है; इस तरह के क्रमचय केवल दो तत्वों का आदान-प्रदान करते हैं, अन्य को स्थिर छोड़ देते हैं।

अंकन

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

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

ऑगस्टिन-लुई कॉची के दो-पंक्ति संकेतन में, one पहली पंक्ति में 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. एस के तत्व पहली पंक्ति में किसी भी क्रम में प्रकट हो सकते हैं। इस क्रमपरिवर्तन को इस प्रकार भी लिखा जा सकता है:

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

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

साइकिल अंकन

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

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

1. एक ओपनिंग ब्रैकेट लिखें और फिर एक मनमाना तत्व x का चयन करें $S$ और इसे लिखो: $(\,x$
2. फिर एक्स की कक्षा का पता लगाएं; अर्थात्, के क्रमिक अनुप्रयोगों के तहत इसके मूल्यों को लिखिए $\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. एस के सभी तत्वों को चक्रों में लिखे जाने तक दोहराएं।

तो क्रमपरिवर्तन 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-चक्र को अक्सर चक्र संकेतन से हटा दिया जाता है, बशर्ते कि संदर्भ स्पष्ट हो; S में किसी भी तत्व x के किसी भी चक्र में प्रकट नहीं होने के लिए, एक परोक्ष रूप से माना जाता है $\sigma (x)=x$. पहचान क्रमचय, जिसमें केवल 1-चक्र होते हैं, को एकल 1-चक्र (x) द्वारा संख्या 1 द्वारा निरूपित किया जा सकता है, या आईडी द्वारा। चक्र संकेतन की एक सुविधाजनक विशेषता यह है कि व्युत्क्रम क्रमचय का चक्र अंकन क्रमचय के चक्रों में तत्वों के क्रम को उलट कर दिया जाता है। उदाहरण के लिए,

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

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

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

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

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

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

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

दो क्रमपरिवर्तनों की संरचना को निरूपित करने के दो तरीके हैं। $\sigma \cdot \pi$ वह फ़ंक्शन है जो सेट के किसी तत्व x को मैप करता है $\sigma (\pi (x))$. सबसे सही क्रमचय पहले तर्क पर लागू होता है, फ़ंक्शन एप्लिकेशन लिखे जाने के तरीके के कारण।

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

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

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

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

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

क्रमपरिवर्तन शब्द का एक कमजोर अर्थ, कभी-कभी प्राथमिक संयोजन ग्रंथों में उपयोग किया जाता है, उन आदेशित व्यवस्थाओं को निर्दिष्ट करता है जिनमें कोई तत्व एक से अधिक बार नहीं होता है, लेकिन किसी दिए गए सेट से सभी तत्वों का उपयोग करने की आवश्यकता के बिना। ये विशेष मामलों को छोड़कर क्रमपरिवर्तन नहीं हैं, बल्कि आदेशित व्यवस्था अवधारणा के प्राकृतिक सामान्यीकरण हैं। वास्तव में, इस प्रयोग में अक्सर n आकार के दिए गए सेट से लिए गए तत्वों की एक निश्चित लंबाई k की व्यवस्था पर विचार करना शामिल होता है, दूसरे शब्दों में, ये 'k-क्रमपरिवर्तन' n के k-तत्व उपसमुच्चय की अलग-अलग क्रमबद्ध व्यवस्थाएं हैं। -सेट (कभी-कभी पुराने साहित्य में 'विविधता' या 'व्यवस्था' कहा जाता है)). इन वस्तुओं को आंशिक क्रमपरिवर्तन#प्रतिबंधित आंशिक क्रमपरिवर्तन या पुनरावृत्ति के बिना अनुक्रम के रूप में भी जाना जाता है, ऐसे शब्द जो दूसरे के साथ भ्रम से बचते हैं, अधिक सामान्य, क्रमपरिवर्तन का अर्थ। ऐसे की संख्या $k$-क्रमपरिवर्तन $n$ जैसे विभिन्न प्रतीकों द्वारा निरूपित किया जाता है $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 तत्व उपसमुच्चय लेकर और उनमें से प्रत्येक को सभी संभव तरीकों से क्रमित करके, हम 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 तत्वों की क्रमबद्ध व्यवस्था, जहाँ पुनरावृत्ति की अनुमति है, Tuple|k-tuples कहलाती है। उन्हें कभी-कभी 'पुनरावृत्ति के साथ क्रमपरिवर्तन' के रूप में संदर्भित किया जाता है, हालांकि वे सामान्य रूप से क्रमपरिवर्तन नहीं होते हैं। कुछ संदर्भों में उन्हें अक्षर S के ऊपर शब्द (गणित) भी कहा जाता है। यदि समुच्चय S में n अवयव हैं, तो S के ऊपर k-टुपल्स की संख्या है $n^{k}.$ k-tuple में कोई तत्व कितनी बार प्रकट हो सकता है, इस पर कोई प्रतिबंध नहीं है, लेकिन यदि कोई तत्व कितनी बार प्रकट हो सकता है, इस पर प्रतिबंध लगाया जाता है, तो यह सूत्र अब मान्य नहीं है।

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

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

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

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

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

A k-एक मल्टीसेट M का क्रमपरिवर्तन 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!.

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

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

क्रमचय के चक्र (निश्चित बिंदुओं सहित)। $\sigma$ के साथ एक सेट के n तत्वों का विभाजन जो सेट करता है; इसलिए इन चक्रों की लंबाई का एक विभाजन (संख्या सिद्धांत) बनाते हैं n, जिसे चक्र प्रकार (या कभी-कभी चक्र संरचना या चक्र आकार) कहा जाता है $\sigma$. के प्रत्येक निश्चित बिंदु के लिए चक्र प्रकार में 1 है $\sigma$, प्रत्येक स्थानान्तरण के लिए 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: Parity of a permutation

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

इस परिणाम को बढ़ाया जा सकता है ताकि एक चिन्ह, लिखित रूप में निर्दिष्ट किया जा सके $\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: Permutation matrix

एक क्रमचय मैट्रिक्स एक वर्ग मैट्रिक्स | 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 है जहां निम्न मान वर्तमान मान से बड़ा है। अर्थात्, यदि  = σ₁σ₂...पी_n, तो मैं एक चढ़ाई है अगर σ_i< पृ_i+1.

उदाहरण के लिए, क्रमपरिवर्तन 3452167 में आरोही (स्थितियों पर) 1, 2, 5 और 6 हैं।

इसी तरह, एक अवरोही σ के साथ एक स्थिति i < n है_i> पी_i+1, तो हर मैं के साथ $1\leq i<n$ या तो चढ़ाई है या σ का अवतरण है।

क्रमचय का आरोही क्रम क्रमचय का एक गैर-रिक्त बढ़ता हुआ सन्निहित क्रम है जिसे किसी भी छोर पर नहीं बढ़ाया जा सकता है; यह क्रमिक आरोहण के अधिकतम अनुक्रम से मेल खाता है (बाद वाला खाली हो सकता है: दो क्रमिक अवरोही के बीच अभी भी लंबाई का एक आरोही भाग है)। इसके विपरीत क्रमपरिवर्तन का बढ़ता क्रम अनिवार्य रूप से सन्निहित नहीं है: यह कुछ पदों पर मानों को छोड़ कर क्रमपरिवर्तन से प्राप्त तत्वों का बढ़ता क्रम है। उदाहरण के लिए, क्रमचय 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 अवरोह। एक क्रमचय की अधिकता₁σ₂...पी_n एक सूचकांक जे ऐसा है कि σ_j > j. यदि असमानता सख्त नहीं है (अर्थात, σ_j ≥ j), तो j को कमजोर अतिरेक कहा जाता है। k अधिकता वाले n-क्रमपरिवर्तनों की संख्या k अवरोही वाले n-क्रमपरिवर्तनों की संख्या के साथ मेल खाती है।

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

एक-पंक्ति संकेतन और विहित चक्र संकेतन के बीच एक संबंध है। क्रमपरिवर्तन पर विचार करें $(\,2\,)(\,3\,1\,)$ विहित चक्र अंकन में; यदि हम केवल कोष्ठकों को हटा दें, तो हमें क्रमचय प्राप्त होता है $231$ एक-पंक्ति संकेतन में। डोमिनिक फोटा की संक्रमण लेम्मा इस पत्राचार की प्रकृति को एन-क्रमपरिवर्तन (स्वयं के लिए) के सेट पर एक आक्षेप के रूप में स्थापित करती है। रिचर्ड पी। स्टेनली इस पत्राचार को मौलिक आपत्ति कहते हैं। होने देना $f(p)=q$ कोष्ठक-मिटाने वाला परिवर्तन जो वापस आता है $q$ दिए जाने पर एक-पंक्ति संकेतन में $p$ विहित चक्र संकेतन में। जैसा कि कहा गया, $f$ सभी कोष्ठकों को हटाकर संचालित होता है। उलटा परिवर्तन का संचालन, $f^{-1}(q)=p$, जो लौटता है $p$ दिए जाने पर विहित चक्र संकेतन में $q$ एक-पंक्ति संकेतन में, थोड़ा कम सहज ज्ञान युक्त है। एक-पंक्ति संकेतन को देखते हुए $q=q_{1}q_{2}\cdots q_{n}$, का पहला चक्र $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)$. इसके अलावा, Foata की मैपिंग k-कमजोर बहिर्वाह के साथ n-क्रमपरिवर्तन के साथ n-क्रमपरिवर्तन लेता है k − 1 आरोही। उदाहरण के लिए, (2)(31) = 321 में दो कमजोर एक्सीडेंस हैं (इंडेक्स 1 और 2 पर), जबकि f(321) = 231 एक चढ़ाई है (इंडेक्स 1 पर; यानी 2 से 3 तक)।

व्युत्क्रम

Main article: Inversion (discrete mathematics)

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

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

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

जिसे क्यू-फैक्टोरियल [n] के रूप में भी जाना जाता है (X के स्थान पर q के साथ)_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, डी_n−1, ..., डी₂, डी₁, जहां घ_i एक गैर-ऋणात्मक पूर्णांक है जो i से छोटा है (कोई d . छोड़ सकता है)₁, क्योंकि यह हमेशा 0 होता है, लेकिन इसकी उपस्थिति क्रमचय के बाद के रूपांतरण को वर्णन करने में आसान बनाती है)। इसके बाद पहला कदम फैक्टोरियल संख्या प्रणाली में केवल एन को व्यक्त करना है, जो केवल एक विशेष मिश्रित रेडिक्स प्रतिनिधित्व है, जहां, एन से कम संख्याओं के लिए!, क्रमिक अंकों के लिए आधार (स्थान मान या गुणन कारक) हैं (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 पहले कार्यकाल के लिए किए गए विकल्प का प्रतिनिधित्व करता है σ₁, संख्या डी_n−1 दूसरे कार्यकाल के लिए की गई पसंद का प्रतिनिधित्व करता है σ₂ शेष के बीच n − 1 सेट के तत्व, और बहुत कुछ। अधिक सटीक रूप से, प्रत्येक d_n+1−i शेष तत्वों की संख्या σ शब्द से सख्ती से कम देता है_i. चूंकि वे शेष तत्व कुछ बाद के शब्द . के रूप में बदलने के लिए बाध्य हैं_j, अंक d_n+1−i व्युत्क्रमों (i,j) की गणना करता है जिसमें i को छोटे सूचकांक के रूप में शामिल किया जाता है (मानों की संख्या 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, डी_n−1, ..., डी₂, डी₁ एक आदेशित समुच्चय S के क्रमचय में, कोई S के तत्वों की सूची बढ़ते हुए क्रम से शुरू कर सकता है, और i के लिए 1 से n समुच्चय σ तक बढ़ रहा है_i सूची में उस तत्व के लिए जो d . से पहले है_n+1−i अन्य, और उस तत्व को सूची से हटा दें। व्युत्क्रम तालिका को परिवर्तित करने के लिए d_n, डी_n−1, ..., डी₂, डी₁ इसी क्रमपरिवर्तन में, कोई d . से संख्याओं को पार कर सकता है₁ घ_n प्रारंभिक रूप से खाली अनुक्रम में सबसे बड़े से छोटे से S के तत्वों को सम्मिलित करते समय; व्युत्क्रम तालिका से संख्या d का उपयोग करते हुए कदम पर, S से तत्व उस बिंदु पर अनुक्रम में डाला जाता है जहां यह पहले से मौजूद d तत्वों से पहले होता है। वैकल्पिक रूप से कोई व्युत्क्रम तालिका से संख्या और S के तत्वों को विपरीत क्रम में संसाधित कर सकता है, जो n खाली स्लॉट की एक पंक्ति से शुरू होता है, और प्रत्येक चरण में तत्व को S से खाली स्लॉट में रखता है जो d अन्य खाली से पहले होता है स्लॉट।

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

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

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

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

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

Main article: Fisher–Yates shuffle

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]