यादृच्छिक क्रमचय: Difference between revisions
(Created page with "{{Short description|Sequence where any order is equally likely}} एक यादृच्छिक क्रमचय वस्तुओं के एक सेट का ए...") |
(TEXT) |
||
| Line 1: | Line 1: | ||
{{Short description|Sequence where any order is equally likely}} | {{Short description|Sequence where any order is equally likely}} | ||
एक यादृच्छिक | एक यादृच्छिक क्रमपरिवर्तन वस्तुओं के समुच्चय का यादृच्छिक क्रम है, जो कि एक क्रमपरिवर्तन-मूल्यवान यादृच्छिक चर है। यादृच्छिक क्रम[[परिवर्तन]] का उपयोग प्रायः उन क्षेत्रों के लिए मौलिक होता है जो [[कोडिंग सिद्धांत]], [[क्रिप्टोग्राफी]] और [[सिमुलेशन|अनुकार]] जैसे [[यादृच्छिक एल्गोरिदम]] का उपयोग करते हैं। एक यादृच्छिक क्रमपरिवर्तन का एक अच्छा उदाहरण एक [[ताश का पत्ता|ताश के पत्तों]] की गड्डी का फेरबदल (शफल) है: यह आदर्श रूप से 52 पत्तों का एक यादृच्छिक क्रमपरिवर्तन है। | ||
== यादृच्छिक क्रमपरिवर्तन उत्पन्न करना == | == यादृच्छिक क्रमपरिवर्तन उत्पन्न करना == | ||
=== | === प्रवेश-दर-प्रवेश ब्रूट बल विधि === | ||
लंबाई n | लंबाई n के समुच्चय का एक यादृच्छिक क्रमपरिवर्तन यादृच्छिक समान रूप से उत्पन्न करने की एक विधि (अर्थात्, प्रत्येक n! क्रमपरिवर्तन समान रूप से प्रकट होने की संभावना है) क्रम से 1 और n के मध्य एक यादृच्छिक संख्या लेकर एक [[अनुक्रम]] उत्पन्न करना है, यह सुनियत करना कि कोई पुनरावृत्ति नहीं है, और क्रमपरिवर्तन के रूप में इस क्रम (''x''<sub>1</sub>, ..., ''x<sub>n</sub>'') की व्याख्या करना | ||
: <math>\begin{pmatrix} | : <math>\begin{pmatrix} | ||
| Line 11: | Line 11: | ||
x_1 & x_2 & x_3 & \cdots & x_n \\ | x_1 & x_2 & x_3 & \cdots & x_n \\ | ||
\end{pmatrix},</math> | \end{pmatrix},</math> | ||
यहाँ | यहाँ दो-पंक्ति संकेतन में दिखाया गया है। | ||
इस ब्रूट- | इस ब्रूट-बल विधि को कभी-कभी पुनर्प्रयास की आवश्यकता होगी जब भी चयन किया गया यादृच्छिक संख्या पहले से चयनित संख्या की पुनरावृत्ति हो। इससे बचा जा सकता है, यदि, iवें चरण पर (जब ''x''<sub>1</sub>, ..., ''x<sub>i</sub>'' <sub>− 1</sub> का पहले ही चयन किया गया है), एक यादृच्छिक रूप से 1 और ''n'' − ''i'' + 1 के मध्य एक संख्या ''j'' चुनता है और ''x<sub>i</sub>'' को गैर चुनी हुई संख्याओं के ''jवें'' सबसे बड़े समुच्चय के समान करता है। | ||
=== फिशर-येट्स फेरबदल === | === फिशर-येट्स फेरबदल === | ||
फिशर-येट्स | फिशर-येट्स फेरबदल के रूप में जाने वाले एक सरल एल्गोरिद्म बिना किसी पुनर्प्रयास के यादृच्छिक रूप से समान रूप से ''n'' वस्तुओ का क्रमपरिवर्तन उत्पन्न करने के लिए, एक सरल एल्गोरिथ्म किसी भी क्रमपरिवर्तन (उदाहरण के लिए, [[पहचान समारोह|पहचान क्रमपरिवर्तन]]) के साथ प्रारंभ करना है, और फिर स्थिति 0 से ''n'' − 2 तक जाना है। (हम एक सम्मेलन का उपयोग करते हैं जहां पहले तत्व का सूचकांक 0 है, और अंतिम तत्व का सूचकांक ''n'' − 1 है), और प्रत्येक स्थिति के लिए ''i'' वर्तमान में उपस्तिथ तत्व को यादृच्छिक रूप से चयन किए गए तत्व के साथ स्थिति ''i'' से ''n − 1'' (अंत) तक <nowiki>''स्वैप''</nowiki> करता है। यह प्रमाणित करना आसान है कि ''n'' तत्वों का कोई भी क्रमपरिवर्तन इस[[ कलन विधि | एल्गोरिथम]] द्वारा बिल्कुल ''1/n!'' की प्रायिकता के साथ निर्मित किया जाएगा, इस प्रकार ऐसे सभी क्रमपरिवर्तनों पर एक समान वितरण प्राप्त होगा। | ||
<syntaxhighlight lang="c"> | <syntaxhighlight lang="c"> | ||
| Line 30: | Line 30: | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
ध्यान दें कि यदि <code>uniform()</code> | ध्यान दें कि यदि <code>uniform()</code> फलन के <code>random() % (m)</code> के रूप में कार्यान्वित किया जाता है, तो परिणामों में पूर्वाग्रह प्रस्तावित किया जाता है यदि <code>random()</code> के रिटर्न मानों की संख्या m के एक से अधिक नहीं है, लेकिन यह नगण्य हो जाता है यदि <code>random()</code> रिटर्न मूल्यों की संख्या m से अधिक परिमाण का क्रम है। | ||
== यादृच्छिक क्रमपरिवर्तन पर | == यादृच्छिक क्रमपरिवर्तन पर सांख्यिकी == | ||
=== | === नियत बिंदु === | ||
{{main| | {{main|रेनकंट्रेस संख्याएं}} | ||
एक समान रूप से वितरित यादृच्छिक | |||
एक समान रूप से वितरित यादृच्छिक क्रमपरिवर्तन में [[निश्चित बिंदु (गणित)|नियत बिंदुओं (गणित)]] की संख्या का प्रायिकता वितरण, ''n'' बढ़ने पर अपेक्षित मान 1 के साथ पॉइसन वितरण तक पहुंचता है। विशेष रूप से, यह दिखाने के लिए समावेशन-अपवर्जन सिद्धांत का एक परिष्कृत अनुप्रयोग है कि कोई नियत बिंदु नहीं होने की संभावना ''1/e'' तक पहुंचती है। जब ''n'' पर्याप्त बड़ा होता है, तो नियत बिंदुओं का [[प्रायिकता वितरण]] अपेक्षित मान 1 के साथ लगभग पोइसन वितरण होता है।<ref>{{Cite journal|last=Durstenfeld|first=Richard|date=1964-07-01|title=Algorithm 235: Random permutation|url=http://portal.acm.org/citation.cfm?doid=364520.364540|journal=Communications of the ACM|volume=7|issue=7|pages=420|doi=10.1145/364520.364540}}</ref> इस वितरण के पहले ''n'' क्षण बिल्कुल पॉइसन वितरण के हैं। | |||
== [[यादृच्छिकता परीक्षण]] == | == [[यादृच्छिकता परीक्षण]] == | ||
जैसा कि सभी यादृच्छिक प्रक्रियाओं के साथ होता है, एक यादृच्छिक एल्गोरिथम के कार्यान्वयन के परिणामी वितरण की गुणवत्ता जैसे कि नुथ शफल (यानी, | जैसा कि सभी यादृच्छिक प्रक्रियाओं के साथ होता है, एक यादृच्छिक एल्गोरिथम के कार्यान्वयन के परिणामी वितरण की गुणवत्ता जैसे कि नुथ शफल (यानी, अपेक्षित समान वितरण के कितने समीप है) यादृच्छिकता के अंतर्निहित स्रोत की गुणवत्ता पर निर्भर करता है, जैसे कि एक [[छद्म यादृच्छिक संख्या जनरेटर|कूट यादृच्छिक संख्या उत्पादक]]। यादृच्छिक क्रमपरिवर्तन के लिए कई संभावित यादृच्छिकता परीक्षण हैं, जैसे कि कुछ डाईहार्ड परीक्षण है। इस तरह के परीक्षण का एक विशिष्ट उदाहरण कुछ क्रमपरिवर्तन आँकड़े लेना है जिसके लिए वितरण ज्ञात है और परीक्षण करें कि यादृच्छिक रूप से उत्पन्न किए गए क्रमपरिवर्तन के समुच्चय पर इस आंकड़े का वितरण सही वितरण के पास है या नहीं। | ||
== यह भी देखें == | == यह भी देखें == | ||
* इवेन्स | * इवेन्स प्रतिचयन सूत्र - [[जनसंख्या आनुवंशिकी]] के साथ एक संबंध | ||
* फ़ारो फेरबदल | * फ़ारो फेरबदल | ||
* गोलोम्ब-डिकमैन स्थिरांक | * गोलोम्ब-डिकमैन स्थिरांक | ||
* यादृच्छिक क्रमपरिवर्तन | * यादृच्छिक क्रमपरिवर्तन सांख्यिकी | ||
* | * फेरबदल एल्गोरिदम - यादृच्छिक सॉर्ट विधि, पुनरावृत्त विनिमय विधि | ||
* [[छद्म आयामी क्रमपरिवर्तन]] | * [[छद्म आयामी क्रमपरिवर्तन]] | ||
Revision as of 00:15, 29 March 2023
एक यादृच्छिक क्रमपरिवर्तन वस्तुओं के समुच्चय का यादृच्छिक क्रम है, जो कि एक क्रमपरिवर्तन-मूल्यवान यादृच्छिक चर है। यादृच्छिक क्रमपरिवर्तन का उपयोग प्रायः उन क्षेत्रों के लिए मौलिक होता है जो कोडिंग सिद्धांत, क्रिप्टोग्राफी और अनुकार जैसे यादृच्छिक एल्गोरिदम का उपयोग करते हैं। एक यादृच्छिक क्रमपरिवर्तन का एक अच्छा उदाहरण एक ताश के पत्तों की गड्डी का फेरबदल (शफल) है: यह आदर्श रूप से 52 पत्तों का एक यादृच्छिक क्रमपरिवर्तन है।
यादृच्छिक क्रमपरिवर्तन उत्पन्न करना
प्रवेश-दर-प्रवेश ब्रूट बल विधि
लंबाई n के समुच्चय का एक यादृच्छिक क्रमपरिवर्तन यादृच्छिक समान रूप से उत्पन्न करने की एक विधि (अर्थात्, प्रत्येक n! क्रमपरिवर्तन समान रूप से प्रकट होने की संभावना है) क्रम से 1 और n के मध्य एक यादृच्छिक संख्या लेकर एक अनुक्रम उत्पन्न करना है, यह सुनियत करना कि कोई पुनरावृत्ति नहीं है, और क्रमपरिवर्तन के रूप में इस क्रम (x1, ..., xn) की व्याख्या करना
यहाँ दो-पंक्ति संकेतन में दिखाया गया है।
इस ब्रूट-बल विधि को कभी-कभी पुनर्प्रयास की आवश्यकता होगी जब भी चयन किया गया यादृच्छिक संख्या पहले से चयनित संख्या की पुनरावृत्ति हो। इससे बचा जा सकता है, यदि, iवें चरण पर (जब x1, ..., xi − 1 का पहले ही चयन किया गया है), एक यादृच्छिक रूप से 1 और n − i + 1 के मध्य एक संख्या j चुनता है और xi को गैर चुनी हुई संख्याओं के jवें सबसे बड़े समुच्चय के समान करता है।
फिशर-येट्स फेरबदल
फिशर-येट्स फेरबदल के रूप में जाने वाले एक सरल एल्गोरिद्म बिना किसी पुनर्प्रयास के यादृच्छिक रूप से समान रूप से n वस्तुओ का क्रमपरिवर्तन उत्पन्न करने के लिए, एक सरल एल्गोरिथ्म किसी भी क्रमपरिवर्तन (उदाहरण के लिए, पहचान क्रमपरिवर्तन) के साथ प्रारंभ करना है, और फिर स्थिति 0 से n − 2 तक जाना है। (हम एक सम्मेलन का उपयोग करते हैं जहां पहले तत्व का सूचकांक 0 है, और अंतिम तत्व का सूचकांक n − 1 है), और प्रत्येक स्थिति के लिए i वर्तमान में उपस्तिथ तत्व को यादृच्छिक रूप से चयन किए गए तत्व के साथ स्थिति i से n − 1 (अंत) तक ''स्वैप'' करता है। यह प्रमाणित करना आसान है कि n तत्वों का कोई भी क्रमपरिवर्तन इस एल्गोरिथम द्वारा बिल्कुल 1/n! की प्रायिकता के साथ निर्मित किया जाएगा, इस प्रकार ऐसे सभी क्रमपरिवर्तनों पर एक समान वितरण प्राप्त होगा।
unsigned uniform(unsigned m); /* Returns a random integer 0 <= uniform(m) <= m-1 with uniform distribution */
void initialize_and_permute(unsigned permutation[], unsigned n)
{
unsigned i;
for (i = 0; i <= n-2; i++) {
unsigned j = i+uniform(n-i); /* A random integer such that i ≤ j < n */
swap(permutation[i], permutation[j]); /* Swap the randomly picked element with permutation[i] */
}
}
ध्यान दें कि यदि uniform() फलन के random() % (m) के रूप में कार्यान्वित किया जाता है, तो परिणामों में पूर्वाग्रह प्रस्तावित किया जाता है यदि random() के रिटर्न मानों की संख्या m के एक से अधिक नहीं है, लेकिन यह नगण्य हो जाता है यदि random() रिटर्न मूल्यों की संख्या m से अधिक परिमाण का क्रम है।
यादृच्छिक क्रमपरिवर्तन पर सांख्यिकी
नियत बिंदु
एक समान रूप से वितरित यादृच्छिक क्रमपरिवर्तन में नियत बिंदुओं (गणित) की संख्या का प्रायिकता वितरण, n बढ़ने पर अपेक्षित मान 1 के साथ पॉइसन वितरण तक पहुंचता है। विशेष रूप से, यह दिखाने के लिए समावेशन-अपवर्जन सिद्धांत का एक परिष्कृत अनुप्रयोग है कि कोई नियत बिंदु नहीं होने की संभावना 1/e तक पहुंचती है। जब n पर्याप्त बड़ा होता है, तो नियत बिंदुओं का प्रायिकता वितरण अपेक्षित मान 1 के साथ लगभग पोइसन वितरण होता है।[1] इस वितरण के पहले n क्षण बिल्कुल पॉइसन वितरण के हैं।
यादृच्छिकता परीक्षण
जैसा कि सभी यादृच्छिक प्रक्रियाओं के साथ होता है, एक यादृच्छिक एल्गोरिथम के कार्यान्वयन के परिणामी वितरण की गुणवत्ता जैसे कि नुथ शफल (यानी, अपेक्षित समान वितरण के कितने समीप है) यादृच्छिकता के अंतर्निहित स्रोत की गुणवत्ता पर निर्भर करता है, जैसे कि एक कूट यादृच्छिक संख्या उत्पादक। यादृच्छिक क्रमपरिवर्तन के लिए कई संभावित यादृच्छिकता परीक्षण हैं, जैसे कि कुछ डाईहार्ड परीक्षण है। इस तरह के परीक्षण का एक विशिष्ट उदाहरण कुछ क्रमपरिवर्तन आँकड़े लेना है जिसके लिए वितरण ज्ञात है और परीक्षण करें कि यादृच्छिक रूप से उत्पन्न किए गए क्रमपरिवर्तन के समुच्चय पर इस आंकड़े का वितरण सही वितरण के पास है या नहीं।
यह भी देखें
- इवेन्स प्रतिचयन सूत्र - जनसंख्या आनुवंशिकी के साथ एक संबंध
- फ़ारो फेरबदल
- गोलोम्ब-डिकमैन स्थिरांक
- यादृच्छिक क्रमपरिवर्तन सांख्यिकी
- फेरबदल एल्गोरिदम - यादृच्छिक सॉर्ट विधि, पुनरावृत्त विनिमय विधि
- छद्म आयामी क्रमपरिवर्तन
संदर्भ
- ↑ Durstenfeld, Richard (1964-07-01). "Algorithm 235: Random permutation". Communications of the ACM. 7 (7): 420. doi:10.1145/364520.364540.
बाहरी संबंध
- Random permutation at MathWorld
- Random permutation generation -- detailed and practical explanation of Knuth shuffle algorithm and its variants for generating k-permutations (permutations of k elements chosen from a list) and k-subsets (generating a subset of the elements in the list without replacement) with pseudocode
