यादृच्छिक क्रमचय: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Sequence where any order is equally likely}} एक यादृच्छिक क्रमचय वस्तुओं के एक सेट का ए...")
 
No edit summary
 
(6 intermediate revisions by 5 users not shown)
Line 1: Line 1:
{{Short description|Sequence where any order is equally likely}}
{{Short description|Sequence where any order is equally likely}}
एक यादृच्छिक क्रमचय वस्तुओं के एक सेट का एक यादृच्छिक क्रम है, जो कि एक क्रमचय-मूल्यवान यादृच्छिक चर है। यादृच्छिक क्रम[[परिवर्तन]] का उपयोग अक्सर उन क्षेत्रों के लिए मौलिक होता है जो [[कोडिंग सिद्धांत]], [[क्रिप्टोग्राफी]] और [[सिमुलेशन]] जैसे [[यादृच्छिक एल्गोरिदम]] का उपयोग करते हैं। एक यादृच्छिक क्रमचय का एक अच्छा उदाहरण एक [[ताश का पत्ता]] का फेरबदल है: यह आदर्श रूप से 52 कार्डों का एक यादृच्छिक क्रमचय है।
एक यादृच्छिक क्रमचय वस्तुओं के समुच्चय का यादृच्छिक क्रम है, जो कि एक क्रमचय-मूल्यवान यादृच्छिक चर है। यादृच्छिक [[परिवर्तन|क्रमचय]] का उपयोग प्रायः उन क्षेत्रों के लिए मौलिक होता है जो [[कोडिंग सिद्धांत]], [[क्रिप्टोग्राफी]] और [[सिमुलेशन|अनुकार]] जैसे [[यादृच्छिक एल्गोरिदम]] का उपयोग करते हैं। एक यादृच्छिक क्रमचय का एक अच्छा उदाहरण एक [[ताश का पत्ता|ताश के पत्तों]] की गड्डी का फेरबदल (शफल) है: यह आदर्श रूप से 52 पत्तों का एक यादृच्छिक क्रमचय है।


== यादृच्छिक क्रमपरिवर्तन उत्पन्न करना ==
== यादृच्छिक क्रमचय उत्पन्न करना ==


=== एंट्री-बाय-एंट्री ब्रूट फोर्स मेथड ===
=== प्रवेश-दर-प्रवेश ब्रूट बल विधि ===
लंबाई n [[समान वितरण (असतत)]] के एक सेट का एक यादृच्छिक क्रमचय उत्पन्न करने की एक विधि (अर्थात्, प्रत्येक n! क्रमपरिवर्तन समान रूप से प्रकट होने की संभावना है) 1 और n क्रमिक रूप से एक यादृच्छिक संख्या लेकर एक [[अनुक्रम]] उत्पन्न करना है, यह सुनिश्चित करना कोई दोहराव नहीं है, और इस क्रम की व्याख्या (x<sub>1</sub>, ..., एक्स<sub>''n''</sub>) क्रमचय के रूप में
लंबाई 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>, ..., एक्स<sub>''i'' &minus; 1</sub> पहले से ही चुना जा चुका है), एक यादृच्छिक रूप से 1 और n − i + 1 के बीच एक संख्या j चुनता है और x सेट करता है<sub>''i''</sub> अचयनित संख्याओं के जेवें सबसे बड़े के बराबर।
इस ब्रूट-बल विधि को कभी-कभी पुनर्प्रयास की आवश्यकता होगी जब भी चुनी गयी यादृच्छिक संख्या पहले से चयनित संख्या की पुनरावृत्ति होगी। इससे बचा जा सकता है, यदि, iवें चरण पर (जब ''x''<sub>1</sub>, ..., ''x<sub>i</sub>'' <sub>− 1</sub> का पहले ही चयन किया हो), एक यादृच्छिक रूप से 1 और ''n'' − ''i'' + 1 के मध्य एक संख्या ''j'' चयन करता है और ''x<sub>i</sub>'' को अचयनित संख्याओं के ''jवें''  सबसे बड़े समुच्चय के समान करता है।


=== फिशर-येट्स फेरबदल ===
=== फिशर-येट्स शफल ===
फिशर-येट्स शफल के रूप में जाना जाता है, बिना पुनर्प्रयास के यादृच्छिक रूप से समान रूप से एन वस्तुओं का क्रमपरिवर्तन उत्पन्न करने के लिए एक सरल एल्गोरिथ्म किसी भी क्रमचय (उदाहरण के लिए, [[पहचान समारोह]]) के साथ शुरू करना है, और फिर स्थिति 0 से एन - 2 तक जाना है। (हम एक सम्मेलन का उपयोग करते हैं जहां पहले तत्व में इंडेक्स 0 होता है, और अंतिम तत्व में इंडेक्स एन - 1 होता है), और प्रत्येक स्थिति के लिए मैं वर्तमान में तत्व को यादृच्छिक रूप से चुने गए तत्व के साथ स्थिति i से n - 1 (द) के लिए 'स्वैप' करता हूं। अंत), समावेशी। यह सत्यापित करना आसान है कि n तत्वों का कोई भी क्रमचय इस [[ कलन विधि ]] द्वारा बिल्कुल 1/n! की प्रायिकता के साथ निर्मित किया जाएगा, इस प्रकार ऐसे सभी क्रमपरिवर्तनों पर एक समान वितरण प्राप्त होगा।
फिशर-येट्स शफल के रूप में जाने वाले एक सरल एल्गोरिद्म बिना किसी पुनर्प्रयास के यादृच्छिक समान रूप से ''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>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|Rencontres numbers}}
{{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 क्षण (गणित) वास्तव में प्वासों बंटन का है।
 
एक समान रूप से वितरित यादृच्छिक क्रमचय में [[निश्चित बिंदु (गणित)|नियत बिंदुओं (गणित)]] की संख्या का प्रायिकता वितरण, ''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 56: Line 57:
* [http://mathworld.wolfram.com/RandomPermutation.html Random permutation] at [[MathWorld]]
* [http://mathworld.wolfram.com/RandomPermutation.html Random permutation] at [[MathWorld]]
* [https://web.archive.org/web/20180619075139/http://www.techuser.net/randpermgen.html 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
* [https://web.archive.org/web/20180619075139/http://www.techuser.net/randpermgen.html 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
[[Category: क्रमपरिवर्तन]] [[Category: यादृच्छिक एल्गोरिदम]]


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:Created On 21/03/2023]]
[[Category:Created On 21/03/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:क्रमपरिवर्तन]]
[[Category:यादृच्छिक एल्गोरिदम]]

Latest revision as of 17:27, 17 April 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 से अधिक परिमाण के क्रम है।

यादृच्छिक क्रमचय पर सांख्यिकी

नियत बिंदु

Main article: रेनकंट्रेस संख्याएं

एक समान रूप से वितरित यादृच्छिक क्रमचय में नियत बिंदुओं (गणित) की संख्या का प्रायिकता वितरण, n बढ़ने पर अपेक्षित मान 1 के साथ पॉइसन वितरण तक पहुंचता है। विशेष रूप से, यह दिखाने के लिए समावेशन-अपवर्जन सिद्धांत का एक परिष्कृत अनुप्रयोग है कि कोई नियत बिंदु नहीं होने की संभावना 1/e तक पहुंचती है। जब n पर्याप्त बड़ा होता है, तो नियत बिंदुओं का प्रायिकता वितरण अपेक्षित मान 1 के साथ लगभग पोइसन वितरण होता है।[1] इस वितरण के पहले n क्षण बिल्कुल पॉइसन वितरण के हैं।

यादृच्छिकता परीक्षण

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

यह भी देखें

  • इवेन्स प्रतिचयन सूत्र - जनसंख्या आनुवंशिकी के साथ एक संबंध
  • फ़ारो शफल
  • गोलोम्ब-डिकमैन स्थिरांक
  • यादृच्छिक क्रमचय सांख्यिकी
  • शफल एल्गोरिदम - यादृच्छिक सॉर्ट विधि, पुनरावृत्त विनिमय विधि
  • छद्म आयामी क्रमचय

संदर्भ

  1. ↑ 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
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=यादृच्छिक_क्रमचय&oldid=134183’