यादृच्छिक क्रमचय: Difference between revisions
(TEXT) |
No edit summary |
||
| 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 16: | Line 16: | ||
=== फिशर-येट्स शफल === | === फिशर-येट्स शफल === | ||
फिशर-येट्स शफल के रूप में जाने वाले एक सरल एल्गोरिद्म बिना किसी पुनर्प्रयास के यादृच्छिक समान रूप से ''n'' वस्तुओ का | फिशर-येट्स शफल के रूप में जाने वाले एक सरल एल्गोरिद्म बिना किसी पुनर्प्रयास के यादृच्छिक समान रूप से ''n'' वस्तुओ का क्रमचय उत्पन्न करने के लिए, एक सरल एल्गोरिथ्म किसी भी क्रमचय (उदाहरण के लिए, [[पहचान समारोह|पहचान क्रमचय]]) के साथ प्रारंभ करते है, और फिर स्थिति 0 से ''n'' − 2 तक जाते है (हम एक सम्मेलन का उपयोग करते हैं जहां पहले तत्व का सूचकांक 0 है, और अंतिम तत्व का सूचकांक ''n'' − 1 है), और प्रत्येक स्थिति के लिए ''i'' वर्तमान में उपस्तिथ तत्व को यादृच्छिक रूप से चयन किए गए तत्व के साथ स्थिति ''i'' से ''n − 1'' (अंत) तक <nowiki>''स्वैप''</nowiki> करते है। यह प्रमाणित करना आसान है कि ''n'' तत्वों का कोई भी क्रमचय इस[[ कलन विधि | एल्गोरिथम]] द्वारा बिल्कुल ''1/n!'' की प्रायिकता के साथ निर्मित किया जाएगा, इस प्रकार ऐसे सभी क्रमचयों पर एक समान वितरण प्राप्त करते है। | ||
<syntaxhighlight lang="c"> | <syntaxhighlight lang="c"> | ||
| Line 32: | Line 32: | ||
ध्यान दें कि यदि <code>uniform()</code> फलन को केवल <code>random() % (m)</code> के रूप में कार्यान्वित किया जाता है, तो परिणामों में पूर्वाग्रह प्रस्तावित किया जाता है यदि <code>random()</code> के रिटर्न मानों की संख्या m के एक से अधिक नहीं है, लेकिन यह नगण्य हो जाते है अगर <code>random()</code> के रिटर्न मूल्यों की संख्या m से अधिक परिमाण के क्रम है। | ध्यान दें कि यदि <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'' क्षण बिल्कुल पॉइसन वितरण के हैं। | ||
== [[यादृच्छिकता परीक्षण]] == | == [[यादृच्छिकता परीक्षण]] == | ||
जैसा कि सभी यादृच्छिक प्रक्रियाओं के साथ होता है, एक यादृच्छिक एल्गोरिथम के कार्यान्वयन के परिणामी वितरण की गुणवत्ता जैसे कि नुथ शफल ( | जैसा कि सभी यादृच्छिक प्रक्रियाओं के साथ होता है, एक यादृच्छिक एल्गोरिथम के कार्यान्वयन के परिणामी वितरण की गुणवत्ता जैसे कि नुथ शफल (अर्थात, अपेक्षित समान वितरण के कितने समीप है) यादृच्छिकता के अंतर्निहित स्रोत की गुणवत्ता पर निर्भर करते है, जैसे कि एक [[छद्म यादृच्छिक संख्या जनरेटर|कूट यादृच्छिक संख्या उत्पादक]] है। यादृच्छिक क्रमचय के लिए कई संभावित यादृच्छिकता परीक्षण हैं, जैसे कि कुछ डाईहार्ड परीक्षण है। इस तरह के परीक्षण का एक विशिष्ट उदाहरण कुछ क्रमचय आँकड़े लेना है जिसके लिए वितरण ज्ञात है और परीक्षण करें कि यादृच्छिक रूप से उत्पन्न किए गए क्रमचय के समुच्चय पर इस आंकड़े का वितरण सही वितरण के पास है या नहीं। | ||
== यह भी देखें == | == यह भी देखें == | ||
| Line 46: | Line 46: | ||
* फ़ारो शफल | * फ़ारो शफल | ||
* गोलोम्ब-डिकमैन स्थिरांक | * गोलोम्ब-डिकमैन स्थिरांक | ||
* यादृच्छिक | * यादृच्छिक क्रमचय सांख्यिकी | ||
* शफल एल्गोरिदम - यादृच्छिक सॉर्ट विधि, पुनरावृत्त विनिमय विधि | * शफल एल्गोरिदम - यादृच्छिक सॉर्ट विधि, पुनरावृत्त विनिमय विधि | ||
* [[छद्म आयामी क्रमपरिवर्तन]] | * [[छद्म आयामी क्रमपरिवर्तन|छद्म आयामी क्रमचय]] | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 12:00, 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
