यादृच्छिक क्रमपरिवर्तन
यादृच्छिक क्रमपरिवर्तन वस्तुओं के समुच्चय का यादृच्छिक क्रम में होता है, अर्थात, क्रमपरिवर्तन-मूल्यवान यादृच्छिक वेरिएबल मानी जाती है । और यादृच्छिक क्रमपरिवर्तन का उपयोग सदैव उन क्षेत्रों के लिए मौलिक होता है जोकी कोडिंग सिद्धांत, क्रिप्टोग्राफी और सिमुलेशन जैसे यादृच्छिक एल्गोरिदम का उपयोग करते हैं। जिससे यादृच्छिक क्रमपरिवर्तन का सही उदाहरण सफलिंग का उपयोग किया जाता है: यह आदर्श रूप से 52 कार्डों का यादृच्छिक क्रमपरिवर्तन होते है।
यादृच्छिक क्रमपरिवर्तन उत्पन्न करना
प्रवेश-दर-प्रवेश पाशविक बल विधि
आकार n समान वितरण (असतत) के समुच्चय का यादृच्छिक क्रमपरिवर्तन उत्पन्न करने की विधि (अर्थात , प्रत्येक n! क्रमपरिवर्तन समान रूप से प्रकट होने की संभावना है) क्रमिक रूप से 1 और n के बीच यादृच्छिक संख्या लेकर अनुक्रम उत्पन्न करना है, यह सुनिश्चित करना इसमें कोई दोहराव नहीं है, और इस क्रम की व्याख्या (x)1, ..., एक्सn) क्रमपरिवर्तन के रूप में
समान रूप से यादृच्छिक रूप से आकार n के एक सेट का यादृच्छिक क्रमपरिवर्तन उत्पन्न करने की एक विधि (अर्थात , प्रत्येक n! क्रमपरिवर्तन समान रूप से दिखाई देने की संभावना है) क्रमिक रूप से 1 और n के बीच एक यादृच्छिक संख्या लेकर एक अनुक्रम उत्पन्न करना है, यह सुनिश्चित करना कोई पुनरावृत्ति नहीं है, और इस अनुक्रम (x1, ..., xn) को क्रमपरिवर्तन के रूप में व्याख्या कर रहा है
जहाँ क्रमपरिवर्तन या चक्र संकेतन दो-पंक्ति संकेतन में दिखाया गया है।
इस जब भी चुनी गई यादृच्छिक संख्या पहले से चयनित संख्या की पुनरावृत्ति होती है, तो इस पाशविक -बल विधि को कभी-कभी पुनः प्रयास की आवश्यकता होगी। इससे बचा जा सकता है यदि, iवें वेरिएबल ण पर (जब x1, ..., एक्सi − 1 पहले ही चुने जा चुके हैं), कोई 1 और n - i + 1 के बीच यादृच्छिक रूप से संख्या j चुनता है और x समुच्चय करता हैi न चुनी गई संख्याओं में से जेवीं सबसे बड़ी संख्या के समान ।
जब भी चुनी गई यादृच्छिक संख्या पहले से चयनित संख्या की पुनरावृत्ति होती है, तो इस पाशविक -बल विधि को कभी-कभी पुनः प्रयास की आवश्यकता होगी। इससे बचा जा सकता है, यदि iवें चरण पर (जब x1, ..., xi - 1 पहले ही चुना जा चुका हो), कोई 1 और n - i + 1 के बीच यादृच्छिक रूप से एक संख्या j चुनता है और xi को jवें सबसे बड़े के समान सेट करता है अचयनित संख्याओं में से.
फिशर-येट्स सफलिंग
इस प्रकार से पुन: प्रयास किए बिना यादृच्छिक रूप से समान रूप से n आइटमों का क्रमपरिवर्तन उत्पन्न करने के लिए सरल एल्गोरिदम, जिसे फिशर-येट्स शफल के रूप में जाना जाता है, किसी भी क्रमपरिवर्तन (उदाहरण के लिए, पहचान फ़ंक्शन) से प्रारंभ करना है, और फिर 0 से n - 2 तक की स्थिति से होकर निकलना है। (हम कॉनवेनसन का उपयोग करते हैं जहां प्रथम तत्व का सूचकांक है, और अंतिम तत्व का सूचकांक n - 1 है), और प्रत्येक स्थिति के लिए मैं वर्तमान में उपस्तिथ तत्व को स्थिति 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
