यादृच्छिक क्रमचय

एक यादृच्छिक क्रमचय वस्तुओं के एक सेट का एक यादृच्छिक क्रम है, जो कि एक क्रमचय-मूल्यवान यादृच्छिक चर है। यादृच्छिक क्रमपरिवर्तन का उपयोग अक्सर उन क्षेत्रों के लिए मौलिक होता है जो कोडिंग सिद्धांत, क्रिप्टोग्राफी और सिमुलेशन जैसे यादृच्छिक एल्गोरिदम का उपयोग करते हैं। एक यादृच्छिक क्रमचय का एक अच्छा उदाहरण एक ताश का पत्ता का फेरबदल है: यह आदर्श रूप से 52 कार्डों का एक यादृच्छिक क्रमचय है।

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

एंट्री-बाय-एंट्री ब्रूट फोर्स मेथड

लंबाई n समान वितरण (असतत) के एक सेट का एक यादृच्छिक क्रमचय उत्पन्न करने की एक विधि (अर्थात्, प्रत्येक n! क्रमपरिवर्तन समान रूप से प्रकट होने की संभावना है) 1 और n क्रमिक रूप से एक यादृच्छिक संख्या लेकर एक अनुक्रम उत्पन्न करना है, यह सुनिश्चित करना कोई दोहराव नहीं है, और इस क्रम की व्याख्या (x₁, ..., एक्स_n) क्रमचय के रूप में

${\begin{pmatrix}1&2&3&\cdots &n\\x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\end{pmatrix}},$

यहाँ क्रमपरिवर्तन में दिखाया गया है#चक्र संकेतन|दो-पंक्ति संकेतन।

इस ब्रूट-फोर्स विधि को कभी-कभी पुनर्प्रयास की आवश्यकता होगी जब भी चुना गया यादृच्छिक संख्या पहले से चयनित संख्या का दोहराव हो। इससे बचा जा सकता है, अगर iवें चरण पर (जब x₁, ..., एक्स_{i − 1} पहले से ही चुना जा चुका है), एक यादृच्छिक रूप से 1 और n − i + 1 के बीच एक संख्या j चुनता है और x सेट करता है_i अचयनित संख्याओं के जेवें सबसे बड़े के बराबर।

फिशर-येट्स फेरबदल

फिशर-येट्स शफल के रूप में जाना जाता है, बिना पुनर्प्रयास के यादृच्छिक रूप से समान रूप से एन वस्तुओं का क्रमपरिवर्तन उत्पन्न करने के लिए एक सरल एल्गोरिथ्म किसी भी क्रमचय (उदाहरण के लिए, पहचान समारोह) के साथ शुरू करना है, और फिर स्थिति 0 से एन - 2 तक जाना है। (हम एक सम्मेलन का उपयोग करते हैं जहां पहले तत्व में इंडेक्स 0 होता है, और अंतिम तत्व में इंडेक्स एन - 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 से अधिक परिमाण का क्रम है।

यादृच्छिक क्रमपरिवर्तन पर आँकड़े

निश्चित बिंदु

Main article: Rencontres numbers

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

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

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

यह भी देखें

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

बाहरी संबंध

• 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