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

एक यादृच्छिक क्रमपरिवर्तन वस्तुओं के एक सेट का एक यादृच्छिक क्रम है, अर्थात, एक क्रमपरिवर्तन-मूल्यवान यादृच्छिक चर। यादृच्छिक क्रमपरिवर्तन का उपयोग अक्सर उन क्षेत्रों के लिए मौलिक होता है जो कोडिंग सिद्धांत, क्रिप्टोग्राफी और सिमुलेशन जैसे यादृच्छिक एल्गोरिदम का उपयोग करते हैं। यादृच्छिक क्रमपरिवर्तन का एक अच्छा उदाहरण ताश का पत्ता का फेरबदल है: यह आदर्श रूप से 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 न चुनी गई संख्याओं में से जेवीं सबसे बड़ी संख्या के बराबर।

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

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

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

निश्चित अंक

Main article: Rencontres numbers

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