क्रमचय: Difference between revisions
From Vigyanwiki
| Line 266: | Line 266: | ||
| <math>\mathbf{321}=(\,2\,)(\,3\,1\,)</math> || <math>312=\mathbf{(\,3\,2\,1\,)}</math> | | <math>\mathbf{321}=(\,2\,)(\,3\,1\,)</math> || <math>312=\mathbf{(\,3\,2\,1\,)}</math> | ||
|} | |} | ||
पहले परिणाम के रूप में, ठीक k बाएँ से दाएँ मैक्सिमा के साथ n-क्रमपरिवर्तन की संख्या भी पहली तरह की सांकेतिक स्टर्लिंग संख्या <math>c(n, k)</math> के बराबर है, इसके अलावा, फोटा की मैपिंग k-कमजोर उत्कृष्टता के साथ n-क्रमपरिवर्तन लेती है, {{nowrap|''k'' − 1}} आरोही के साथ n-क्रमपरिवर्तन करती है।{{sfn|Bona|2012|pp=109–110}} उदाहरण के लिए, (2)(31) = 321 में दो कमजोर एक्सीडेंस हैं (इंडेक्स 1 और 2 पर), जबकि {{nowrap|''f''(321) {{=}} 231}} में एक एसेंट (इंडेक्स 1 पर; यानी 2 से 3 तक) है। | |||
=== व्युत्क्रम === | === व्युत्क्रम === | ||
{{main| | {{main|व्युत्क्रम (असतत गणित)}} | ||
[[Image:15-Puzzle.jpg|thumb|[[ 15 पहेली ]] में वर्गों को आरोही क्रम में लाने का लक्ष्य है। प्रारंभिक स्थितियाँ जिनमें विषम संख्या में व्युत्क्रम हैं, को हल करना असंभव है।<ref name="Slocum">{{cite web | [[Image:15-Puzzle.jpg|thumb|[[ 15 पहेली ]] में वर्गों को आरोही क्रम में लाने का लक्ष्य है। प्रारंभिक स्थितियाँ जिनमें विषम संख्या में व्युत्क्रम हैं, को हल करना असंभव है।<ref name="Slocum">{{cite web | ||
| last1 = Slocum | | last1 = Slocum | ||
| Line 280: | Line 280: | ||
| url = http://mathworld.wolfram.com/15Puzzle.html | | url = http://mathworld.wolfram.com/15Puzzle.html | ||
| access-date = October 4, 2014 | | access-date = October 4, 2014 | ||
}}</ref>]] | }}</ref>]]क्रमपरिवर्तन σ का व्युत्क्रम पदों की एक जोड़ी (i, j) है जहां क्रमचय की प्रविष्टियां विपरीत क्रम में होती हैं: <math>\sigma_i > \sigma_j</math>{{sfn|Bóna|2004|p=43}} तो <math>i < j</math> दो आसन्न स्थितियों पर एक व्युत्क्रम है। उदाहरण के लिए, क्रमपरिवर्तन σ = 23154 में तीन व्युत्क्रम हैं: (1, 3), (2, 3), और (4, 5), प्रविष्टियों के जोड़े के लिए (2, 1), (3, 1), और ( 5, 4)। | ||
कभी-कभी व्युत्क्रम को मानों के युग्म | कभी-कभी व्युत्क्रम को मानों के युग्म {{math|(''σ''<sub>''i''</sub>,''σ''<sub>''j''</sub>)}} के रूप में परिभाषित किया जाता है जिसका क्रम व्युत्क्रम होता है; इससे व्युत्क्रमों की संख्या पर कोई फर्क नहीं पड़ता है, और यह जोड़ी (व्युत्क्रम) भी व्युत्क्रम क्रमपरिवर्तन σ<sup>−1</sup> के लिए उपरोक्त अर्थ में एक व्युत्क्रम है। व्युत्क्रम की संख्या उस डिग्री के लिए एक महत्वपूर्ण माप है जिस तक क्रमचय की प्रविष्टियाँ क्रम से बाहर हैं; यह σ और σ<sup>−1</sup> के लिए समान है। K व्युत्क्रमों के साथ एक क्रमचय को क्रम में लाने के लिए (अर्थात, इसे पहचान क्रमपरिवर्तन में रूपांतरित करें), क्रमिक रूप से लागू करके (सही-गुणा द्वारा) आसन्न ट्रांसपोज़िशन, हमेशा संभव है और k ऐसे ऑपरेशनों के अनुक्रम की आवश्यकता होती है। इसके अलावा, आसन्न परिवर्तनों के लिए कोई भी उचित विकल्प काम करेगा: यह प्रत्येक चरण में i और {{nowrap|''i'' + 1}} का स्थानान्तरण चुनने के लिए पर्याप्त है जहाँ i अब तक संशोधित क्रमचय का अवतरण है (ताकि स्थानान्तरण इस विशेष वंश को हटा देगा, हालांकि यह अन्य अवरोही बना सकता है)। ऐसा इसलिए है क्योंकि इस तरह के ट्रांसपोजिशन को लागू करने से व्युत्क्रमों की संख्या 1 कम हो जाती है; जब तक यह संख्या शून्य नहीं है, तब तक क्रमपरिवर्तन पहचान नहीं है, इसलिए इसमें कम से कम एक वंश है। अनुक्रम को क्रम में रखने के लिए [[ बबल शॅाट |बबल शॅाट]] और [[ सम्मिलन सॉर्ट | सम्मिलन सॉर्ट]] को इस प्रक्रिया के विशेष उदाहरणों के रूप में व्याख्या किया जा सकता है। संयोग से यह प्रक्रिया सिद्ध करती है कि किसी भी क्रमचय σ को सन्निकट प्रतिस्थापनों के गुणनफल के रूप में लिखा जा सकता है; इसके लिए कोई ऐसे ट्रांसपोज़िशन के किसी भी क्रम को आसानी से उलट सकता है जो σ को पहचान में बदल देता है। वास्तव में, आसन्न ट्रांसपोज़िशन के सभी अनुक्रमों की गणना करके जो σ को पहचान में बदल देगा, एक (उलटने के बाद) न्यूनतम लंबाई के सभी अभिव्यक्तियों की एक पूरी सूची प्राप्त करता है, जो आसन्न ट्रांसपोज़िशन के उत्पाद के रूप में σ लिखते हैं। | ||
k | k व्युत्क्रम के साथ n के क्रमचय की संख्या एक Mahonian संख्या द्वारा व्यक्त की जाती है,{{sfn|Bóna|2004|pp=43ff}} यह उत्पाद के विस्तार में X<sup>k</sup> का गुणांक है<math display="block">\prod_{m=1}^n\sum_{i=0}^{m-1}X^i = 1 \left(1 + X\right)\left(1 + X + X^2\right) \cdots \left(1 + X + X^2 + \cdots + X^{n-1}\right),</math>जिसे q-फैक्टोरियल [n]q! . उत्पाद का विस्तार [[नेकलेस (कॉम्बिनेटरिक्स)]] में दिखाई देता है। | ||
<math display="block">\prod_{m=1}^n\sum_{i=0}^{m-1}X^i = 1 \left(1 + X\right)\left(1 + X + X^2\right) \cdots \left(1 + X + X^2 + \cdots + X^{n-1}\right),</math> | |||
जिसे | |||
इस मामले में, | माना <math>\sigma \in S_n, i, j\in \{1, 2, \dots, n\} </math> जैसे कि<math>i<j</math> तथा <math>\sigma(i)>\sigma(j)</math>। इस मामले में, मान लें कि व्युत्क्रम <math>(i, j)</math> <math>\sigma(i)-\sigma(j)</math>। | ||
कोबायाशी (2011) ने गणना सूत्र को सिद्ध किया | |||
कोबायाशी (2011) ने गणना सूत्र को सिद्ध किया<math display="block">\sum_{i<j, \sigma(i)>\sigma(j)}(\sigma(i)-\sigma(j)) = |\{\tau \in S_n \mid \tau\le \sigma, \tau \text{ is bigrassmannian}\}</math>जहाँ <math>\le</math> सममित समूहों में ब्रुहट क्रम को दर्शाता है। यह वर्गीकृत आंशिक क्रम अक्सर कॉक्सेटर समूहों के संदर्भ में प्रकट होता है। | |||
== कंप्यूटिंग में क्रमपरिवर्तन == | == कंप्यूटिंग में क्रमपरिवर्तन == | ||
=== क्रमचय क्रमचय === | === क्रमचय क्रमचय === | ||
n चीज़ों के क्रमचयों को निरूपित करने का एक तरीका 0 ≤ N <n! के साथ एक पूर्णांक N है, बशर्ते संख्या और क्रमचय के निरूपण को क्रमबद्ध व्यवस्था (अनुक्रम) के रूप में परिवर्तित करने के लिए सुविधाजनक तरीके दिए गए हों। यह स्वैच्छिक क्रमपरिवर्तन का सबसे कॉम्पैक्ट प्रतिनिधित्व देता है, और कंप्यूटिंग में विशेष रूप से आकर्षक होता है जब n इतना छोटा होता है कि N को एक मशीन शब्द में रखा जा सकता है; 32-बिट शब्दों के लिए इसका अर्थ है n ≤ 12, और 64-बिट शब्दों के लिए इसका अर्थ है n ≤ 20। रूपांतरण संख्याओं के अनुक्रम के मध्यवर्ती रूप के माध्यम से किया जा सकता है d<sub>n</sub>, d<sub>n−1</sub>, ..., d<sub>2</sub>, d<sub>1</sub>, जहाँ di एक गैर-ऋणात्मक पूर्णांक है जो i से कम है (कोई d<sub>1</sub> को छोड़ सकता है, क्योंकि यह हमेशा 0 होता है, लेकिन इसकी उपस्थिति बाद के रूपांतरण को क्रमचय में वर्णित करना आसान बनाती है)। इसके बाद पहला कदम क्रम संख्या प्रणाली में केवल N को व्यक्त करना है, जो सिर्फ एक विशेष मिश्रित मूलांक प्रतिनिधित्व है, जहां, n! से कम संख्याओं के लिए, उत्तरोत्तर अंकों {{nowrap|(''n'' − 1)!}}, {{nowrap|(''n'' − 2)!}}, ..., 2!, 1! के लिए आधार स्थानीय मान या गुणन कारक हैं। दूसरा चरण इस अनुक्रम को एक [[ लेहमर कोड | लेहमर कोड]] या (लगभग समतुल्य) एक व्युत्क्रम तालिका के रूप में व्याख्या करता है। | |||
n | |||
{| class="wikitable" style="float:right; text-align:center; margin: 1em" | {| class="wikitable" style="float:right; text-align:center; margin: 1em" | ||
| Line 345: | Line 341: | ||
| 3 || 6 || 1 || 2 || 4 || 0 || 2 || 0 || 0 || | | 3 || 6 || 1 || 2 || 4 || 0 || 2 || 0 || 0 || | ||
|} | |} | ||
क्रमचय σ के लिए लेह्मर कोड में, संख्या ''d''<sub>''n''</sub> पहले पद σ<sub>1</sub> के लिए किए गए चुनाव को दर्शाती है, संख्या d<sub>n−1</sub> सेट के शेष n − 1 तत्वों के बीच दूसरे पद σ<sub>2</sub> के लिए किए गए चुनाव का प्रतिनिधित्व करती है, और आगे भी। अधिक सटीक रूप से, प्रत्येक d<sub>n+1−i</sub> शेष तत्वों की संख्या σ<sub>i</sub> शब्द से सख्ती से कम देता है। चूंकि वे शेष तत्व कुछ बाद के शब्द σ<sub>j</sub> के रूप में आने के लिए बाध्य हैं, अंक d<sub>''n''+1−''i''</sub> व्युत्क्रमों (i, j) को छोटे सूचकांक के रूप में शामिल करता है (मानों की संख्या j जिसके लिए i < j और σ<sub>i</sub> > σ<sub>j</sub>)। σ के लिए व्युत्क्रम तालिका काफी समान है, लेकिन यहाँ ''d''<sub>''n''+1−''k''</sub> व्युत्क्रमों की संख्या की गणना करता है (i,j) जहाँ k = σ<sub>j</sub> उल्टे क्रम में प्रदर्शित होने वाले दो मानों में से छोटे के रूप में होता है।{{sfn|Knuth|1973|p=12}} दोनों एनकोडिंग को n by n 'रोथ डायग्राम' द्वारा देखा जा सकता है{{#tag:ref|[[Heinrich August Rothe|H. A. Rothe]], ''Sammlung combinatorisch-analytischer Abhandlungen'' '''2''' (Leipzig, 1800), 263–305. Cited in {{harvnb|Knuth|1973|p=14}}}} | |||
σ<sub>2</sub> | |||
([[ हेनरिक अगस्त रोथ |हेनरिक अगस्त रोथ]] के नाम पर) जिसमें बिंदु (i,σ<sub>i</sub>) क्रमपरिवर्तन की प्रविष्टियों को चिह्नित करते हैं, और (i,σ<sub>j</sub>) पर एक क्रॉस व्युत्क्रम (i,j) को चिह्नित करता है; व्युत्क्रम की परिभाषा के अनुसार एक क्रॉस किसी भी वर्ग में प्रकट होता है जो अपने कॉलम में बिंदु (j,σ<sub>j</sub>) से पहले और इसकी पंक्ति में बिंदु (i,σ<sub>i</sub>) दोनों से पहले आता है। लेहमर कोड क्रमिक पंक्तियों में क्रॉस की संख्या को सूचीबद्ध करता है, जबकि उलटा तालिका लगातार कॉलम में क्रॉस की संख्या सूचीबद्ध करती है; यह व्युत्क्रम क्रमचय के लिए लेहमर कोड है, और इसके विपरीत। | |||
प्रभावी रूप से एक लेह्मर कोड d<sub>''n''</sub>, d<sub>''n''−1</sub>, ..., d<sub>2</sub>, d<sub>1</sub> को क्रमित समुच्चय S के क्रमचय में परिवर्तित करने के लिए, कोई S के तत्वों की सूची बढ़ते हुए क्रम से शुरू कर सकता है, और i के लिए 1 से n सेट σi से बढ़ कर उस सूची में उस तत्व के लिए जो d<sub>n+1−i</sub> अन्य से पहले है, और उस तत्व को सूची से हटा दें। एक व्युत्क्रम तालिका d<sub>n</sub>, d<sub>n−1</sub>, ..., d<sub>2</sub>, d<sub>1</sub> को संगत क्रमचय में बदलने के लिए, प्रारंभिक रूप से खाली अनुक्रम में S के तत्वों को सबसे बड़े से सबसे छोटे तक सम्मिलित करते हुए कोई भी d<sub>1</sub> से d<sub>n</sub> तक की संख्या को पार कर सकता है; व्युत्क्रम तालिका से संख्या d का उपयोग करते हुए चरण में, S से तत्व उस बिंदु पर अनुक्रम में डाला जाता है जहां यह पहले से मौजूद d तत्वों से पहले होता है। वैकल्पिक रूप से कोई व्युत्क्रम तालिका से संख्या और एस के तत्वों को विपरीत क्रम में संसाधित कर सकता है, n खाली स्लॉट की एक पंक्ति से शुरू होता है, और प्रत्येक चरण में तत्व को S से खाली स्लॉट में रखें जो d अन्य खाली स्लॉट से पहले हो। | |||
क्रमिक प्राकृतिक संख्याओं को भाज्य संख्या प्रणाली में परिवर्तित करने से उन अनुक्रमों को [[ लेक्सिकोग्राफिक ऑर्डर |लेक्सिकोग्राफिक क्रम]] में उत्पन्न होता है (जैसा कि किसी भी मिश्रित मूलांक संख्या प्रणाली के मामले में होता है), और आगे उन्हें क्रमपरिवर्तन में परिवर्तित करने से लेक्सिकोग्राफिक ऑर्डरिंग बरकरार रहती है, बशर्ते लेहमर कोड व्याख्या का उपयोग किया जाता है (इनवर्जन टेबल का उपयोग करके, एक अलग ऑर्डरिंग मिलती है, जहां कोई अपनी प्रविष्टियों के स्थान 1 के बजाय उनकी पहली प्रविष्टियों के मान से क्रमचय की तुलना करके शुरू करता है)। फैक्टोरियल नंबर सिस्टम प्रतिनिधित्व में संख्याओं का योग क्रमचय के व्युत्क्रमों की संख्या देता है, और उस योग की समानता क्रमचय का [[ हस्ताक्षर (क्रमपरिवर्तन) |हस्ताक्षर (क्रमपरिवर्तन)]] देता है। इसके अतिरिक्त, व्युत्क्रम तालिका में शून्यों की स्थिति क्रमचय के बाएँ से दाएँ उच्चिष्ठ का मान देती है (उदाहरण 6, 8, 9 में) जबकि लेह्मर कोड में शून्य की स्थिति दाएँ-से-बाएँ मिनिमा की स्थिति है (उदाहरण में स्थिति 4, 8, 9 मान 1, 2, 5); यह सभी क्रमपरिवर्तनों के बीच ऐसे एक्स्ट्रेमा के वितरण की गणना करने की अनुमति देता है। लेह्मर कोड d<sub>''n''</sub>, d<sub>''n''−1</sub>, ..., d<sub>2</sub>, d<sub>1</sub> के साथ क्रमचय का आरोहण n − i होता है यदि और केवल यदि {{nowrap|''d''<sub>''i''</sub> ≥ ''d''<sub>''i+1''</sub>}}। | |||
=== क्रमपरिवर्तन उत्पन्न करने के लिए एल्गोरिदम === | === क्रमपरिवर्तन उत्पन्न करने के लिए एल्गोरिदम === | ||
कंप्यूटिंग में मूल्यों के दिए गए अनुक्रम के क्रमपरिवर्तन उत्पन्न करने की आवश्यकता हो सकती है। ऐसा करने के लिए सर्वोत्तम रूप से अनुकूलित विधियां इस बात पर निर्भर करती हैं कि क्या कोई | कंप्यूटिंग में मूल्यों के दिए गए अनुक्रम के क्रमपरिवर्तन उत्पन्न करने की आवश्यकता हो सकती है। ऐसा करने के लिए सर्वोत्तम रूप से अनुकूलित विधियां इस बात पर निर्भर करती हैं कि क्या कोई यादृच्छिक रूप से चुने गए क्रमपरिवर्तन चाहता है, या सभी क्रमपरिवर्तन, और बाद वाले मामले में यदि एक विशिष्ट आदेश की आवश्यकता होती है। एक अन्य प्रश्न यह है कि क्या दिए गए क्रम में प्रविष्टियों के बीच संभावित समानता को ध्यान में रखा जाना चाहिए; यदि ऐसा है, तो किसी को केवल अनुक्रम के अलग-अलग मल्टीसेट क्रमपरिवर्तन उत्पन्न करने चाहिए। | ||
n के क्रमपरिवर्तन उत्पन्न करने का एक स्पष्ट तरीका लेहमर कोड के लिए मान उत्पन्न करना है (संभवतः n तक के पूर्णांकों के भाज्य संख्या प्रणाली प्रतिनिधित्व का उपयोग करके!), और उन्हें संबंधित क्रमपरिवर्तन में परिवर्तित करें। हालाँकि, बाद वाला कदम, जबकि सीधा है, कुशलता से लागू करना कठिन है, क्योंकि इसके लिए एक अनुक्रम से प्रत्येक चयन के लिए n संचालन की आवश्यकता होती है और इसे एक मनमाने स्थान पर हटा दिया जाता है; एक [[ सरणी डेटा संरचना ]] या एक [[ लिंक्ड सूची ]] के रूप में अनुक्रम के स्पष्ट प्रतिनिधित्व के लिए, | n के क्रमपरिवर्तन उत्पन्न करने का एक स्पष्ट तरीका लेहमर कोड के लिए मान उत्पन्न करना है (संभवतः n तक के पूर्णांकों के भाज्य संख्या प्रणाली प्रतिनिधित्व का उपयोग करके!), और उन्हें संबंधित क्रमपरिवर्तन में परिवर्तित करें। हालाँकि, बाद वाला कदम, जबकि सीधा है, कुशलता से लागू करना कठिन है, क्योंकि इसके लिए एक अनुक्रम से प्रत्येक चयन के लिए n संचालन की आवश्यकता होती है और इसे एक मनमाने स्थान पर हटा दिया जाता है; एक [[ सरणी डेटा संरचना |सरणी डेटा संरचना]] या एक [[ लिंक्ड सूची | लिंक्ड सूची]] के रूप में अनुक्रम के स्पष्ट प्रतिनिधित्व के लिए, रूपांतरण करने के लिए n<sub>2/4</sub> संचालन के बारे में (विभिन्न कारणों से) दोनों की आवश्यकता होती है। n के छोटे होने की संभावना के साथ (विशेष रूप से यदि सभी क्रमपरिवर्तनों की पीढ़ी की आवश्यकता है) जो कि बहुत अधिक समस्या नहीं है, लेकिन यह पता चला है कि यादृच्छिक और व्यवस्थित पीढ़ी दोनों के लिए सरल विकल्प हैं जो काफी बेहतर करते हैं। इस कारण से यह उपयोगी प्रतीत नहीं होता है, हालांकि निश्चित रूप से संभव है, एक विशेष डेटा संरचना को नियोजित करने के लिए जो O(n log n) समय में लेह्मर कोड से क्रमचय में रूपांतरण करने की अनुमति देगा। | ||
==== क्रमपरिवर्तन की यादृच्छिक पीढ़ी ==== | ==== क्रमपरिवर्तन की यादृच्छिक पीढ़ी ==== | ||
{{Main| | {{Main|फिशर–येट्स फेरबदल}} | ||
n मानों के दिए गए अनुक्रम के [[ यादृच्छिक क्रमपरिवर्तन ]] उत्पन्न करने के लिए, इससे कोई फर्क नहीं पड़ता है कि अनुक्रम में n का एक यादृच्छिक रूप से चयनित क्रमपरिवर्तन लागू किया जाए, या अनुक्रम के विशिष्ट (मल्टीसेट) क्रमपरिवर्तनों के सेट से एक यादृच्छिक तत्व का चयन किया जाए। ऐसा इसलिए है, क्योंकि दोहराए गए मानों के मामले में n के कई अलग-अलग क्रमपरिवर्तन हो सकते हैं, जिसके परिणामस्वरूप एक ही अनुमत अनुक्रम होता है, ऐसे क्रमपरिवर्तन की संख्या प्रत्येक संभावित परिणाम के लिए समान होती है। व्यवस्थित पीढ़ी के विपरीत, जो संख्या n की वृद्धि के कारण बड़े n के लिए अक्षम्य हो जाता है!, यह मानने का कोई कारण नहीं है कि यादृच्छिक पीढ़ी के लिए n छोटा होगा। | |||
'''n मानों के दिए गए अनुक्रम के [[ यादृच्छिक क्रमपरिवर्तन | यादृच्छिक क्रमपरिवर्तन]] उत्पन्न करने के लिए, इससे कोई फर्क नहीं पड़ता है कि अनुक्रम में n का एक यादृच्छिक रूप से चयनित क्रमपरिवर्तन लागू किया जाए, या अनुक्रम के विशिष्ट (मल्टीसेट) क्रमपरिवर्तनों के सेट से एक यादृच्छिक तत्व का चयन किया जाए। ऐसा इसलिए है, क्योंकि दोहराए गए मानों के मामले में n के कई अलग-अलग क्रमपरिवर्तन हो सकते हैं, जिसके परिणामस्वरूप एक ही अनुमत अनुक्रम होता है, ऐसे क्रमपरिवर्तन की संख्या प्रत्येक संभावित परिणाम के लिए समान होती है। व्यवस्थित पीढ़ी के विपरीत, जो संख्या n की वृद्धि के कारण बड़े n के लिए अक्षम्य हो जाता है!, यह मानने का कोई कारण नहीं है कि यादृच्छिक पीढ़ी के लिए n छोटा होगा।''' | |||
एक यादृच्छिक क्रमचय उत्पन्न करने के लिए मूल विचार n! पूर्णांकों का क्रम d<sub>1</sub>,डी<sub>2</sub>,...,डी<sub>''n''</sub> संतुष्टि देने वाला {{math|0 ≤ ''d''<sub>''i''</sub> < ''i''}} (चूंकि डी<sub>1</sub> हमेशा शून्य होता है इसे छोड़ा जा सकता है) और इसे एक विशेषण पत्राचार के माध्यम से क्रमचय में परिवर्तित करने के लिए। बाद के पत्राचार के लिए लेहमर कोड के रूप में (रिवर्स) अनुक्रम की व्याख्या की जा सकती है, और यह [[ रोनाल्ड फिशर ]] और [[ फ्रैंक येट्स ]] द्वारा पहली बार 1938 में प्रकाशित एक जनरेशन विधि देता है।<ref>{{cite book | एक यादृच्छिक क्रमचय उत्पन्न करने के लिए मूल विचार n! पूर्णांकों का क्रम d<sub>1</sub>,डी<sub>2</sub>,...,डी<sub>''n''</sub> संतुष्टि देने वाला {{math|0 ≤ ''d''<sub>''i''</sub> < ''i''}} (चूंकि डी<sub>1</sub> हमेशा शून्य होता है इसे छोड़ा जा सकता है) और इसे एक विशेषण पत्राचार के माध्यम से क्रमचय में परिवर्तित करने के लिए। बाद के पत्राचार के लिए लेहमर कोड के रूप में (रिवर्स) अनुक्रम की व्याख्या की जा सकती है, और यह [[ रोनाल्ड फिशर ]] और [[ फ्रैंक येट्स ]] द्वारा पहली बार 1938 में प्रकाशित एक जनरेशन विधि देता है।<ref>{{cite book | ||
Revision as of 16:35, 21 November 2022
गणित में, एक सेट का क्रमचय, मोटे तौर पर, इसके सदस्यों की एक अनुक्रम या रैखिक क्रम में व्यवस्था है, या यदि सेट पहले से ही क्रमबद्ध है, तो इसके तत्वों की पुनर्व्यवस्था है।, या यदि समुच्चय पहले से ही क्रमबद्ध है, तो इसके तत्वों की पुनर्व्यवस्था है। शब्द "क्रमचय" भी आदेशित सेट के रैखिक क्रम को बदलने के कार्य या प्रक्रिया को संदर्भित करता है।।[1]
क्रमपरिवर्तन संयोजनों से भिन्न होते हैं, जो क्रम की परवाह किए बिना एक सेट के कुछ सदस्यों के चयन होते हैं। उदाहरण के लिए, टुपल्स के रूप में लिखे गए सेट के छह क्रमपरिवर्तन हैं {1, 2, 3}, अर्थात् (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), और (3, 2, 1)। ये तीन-तत्वों के इस सेट के सभी संभावित क्रम हैं। जिन शब्दों के वर्ण भिन्न हैं उनके एनाग्राम भी क्रमचय हैं: अक्षरों को पहले से ही मूल शब्द में क्रमबद्ध किया गया है, और विपर्यय अक्षरों का पुनर्क्रमण है। साहचर्य और समूह सिद्धांत के क्षेत्र में परिमित सेट के क्रमपरिवर्तन का अध्ययन एक महत्वपूर्ण विषय है।
क्रमपरिवर्तन का उपयोग गणित की लगभग हर शाखा में और विज्ञान के कई अन्य क्षेत्रों में किया जाता है।