Permutare aleatorie

O permutare aleatoare  este o ordonare aleatorie a unui set de obiecte, adică o variabilă aleatoare ale cărei evenimente elementare sunt permutări . Utilizarea permutărilor aleatoare este adesea baza în câmpuri care utilizează algoritmi aleatorii . Astfel de domenii includ teoria codificării , criptografia și modelarea . Un bun exemplu de permutare aleatorie este amestecarea unui pachet de cărți .

Generarea de permutări aleatorii

Metoda directă (element cu element)

O metodă pentru a genera o permutare aleatorie a unui set de n elemente este de a utiliza o distribuție uniformă , care selectează secvențial numere aleatorii între 1 și n , asigurându-se în același timp că nu există repetări. Secvența rezultată ( x 1 , …, x n ) este interpretată ca o permutare

Metoda de generare directă necesită repetarea selecției unui număr aleatoriu dacă numărul extras este deja în secvență. Acest lucru poate fi evitat dacă, la pasul i -a (când sunt deja aleși x 1 , …, x i - 1 ), alegeți un număr aleator j între 1 și n - i + 1 și, apoi, alegeți x i egal cu j --lea număr neales.

Whip Shuffling

Un algoritm simplu pentru generarea de permutări aleatorii a n elemente (distribuite uniform) fără repetări, cunoscut sub numele de amestecare Knuth , începe cu o permutare arbitrară (de exemplu, permutarea identică fără permutarea elementelor) și merge de la poziția 1 la poziția n - 1, permutarea elementului prin pozițiile i cu un element selectat aleatoriu la pozițiile de la i la n inclusiv. Este ușor de arătat că în acest fel obținem toate permutările n elemente cu o probabilitate de exact 1/ n !.

Statistici privind permutările aleatoare

Puncte fixe

Distribuția de probabilitate a numărului de puncte fixe în permutări aleatoare distribuite uniform pe n elemente se apropie de legea lui Poisson pe măsură ce n crește . Numărarea numărului de puncte fixe este un exemplu clasic de utilizare a formulei de includere-excludere , care arată că probabilitatea de lipsă de puncte fixe se apropie de 1/ e . În acest caz, așteptarea matematică a numărului de puncte fixe este egală cu 1 pentru orice dimensiune a permutării. [unu]

Test de aleatorie

Ca și în cazul tuturor proceselor aleatoare, calitatea unui algoritm de generare a permutării, în special algoritmul de amestecare al lui Knuth, depinde de generatorul de numere aleatoare subiacent, cum ar fi generatorul de numere pseudo-aleatoare . Există un număr mare de teste de aleatorie posibile , cum ar fi testele dureroase . Un exemplu tipic al unui astfel de test este alegerea unei statistici pentru care distribuția este cunoscută și verificarea dacă distribuția acestei statistici pe mulțimea de permutări obținute este suficient de apropiată de distribuția reală.

Vezi și

• constanta Golomb-Dickman
• Algoritmi de amestecare  - metoda de sortare aleatorie, metoda permutării iterative
• permutare aleatorie
• Criptanaliză LEX
• Problema a 100 de prizonieri și a 100 de cutii

Note

1. ↑ D. Knuth, R. Graham, O. Patashnik. matematică concretă. - Lumea, 1998.

Literatură

• Jim Pitman. Probabilitate. — Springer Science & Business Media, 2012. — P. 153–. - ISBN 978-1-4612-4374-8 .
• VG Potemkin „Manualul MATLAB” Lucrul cu matrici rare. Este descrisă utilizarea procedurii randperm pentru generarea de permutări aleatorii în pachetul MathLab.
• Alfred W. Aho, John Hopcroft, Jeffrey D. Ullman. Structuri de date și algoritmi. - Editura „Williams”, 2003. - S. 129-130. - ISBN 0-201-00023-7 / 5-8459-0122-7.
• Alfred W Aho, John E Hopcroft, Jeffrey D Ullman. Algoritmi. Construcție și analiză. - Sankt Petersburg, Moscova, Kiev: Editura Williams, 2007. - P. 152-153 Capitolul 5. Analiza probabilistica si algoritmi randomizati.
• Arnold V.I. Observarea experimentală a faptelor matematice . - M. : MTSNMO, 2006. - S.  66 -84. — (Școala de vară „Matematică modernă”). - ISBN 978-5-94057-282-4 .
• T. Christiansen, N. Torkington. perl. Biblioteca programatorului. - Peter, 2001. - S. Capitolul 4 „Matrice” acoperă tot ceea ce ține de operațiunile cu liste și tablouri, inclusiv găsirea elementelor unice, sortarea eficientă și permutarea aleatorie a elementelor .. - ISBN 5-8046-0094-X .
• Kormen T., Leyzerson Ch., Rivest R., Stein K. Algoritmi: construcție și analiză. - M. : „Williams”, 2005. - S. Capitolul 5.3 Algoritmi randomizati. — ISBN 5-8459-0857-4 .
• Boris Nikolaevici Ivanov. Matematică discretă. Algoritmi si programe. Curs avansat. - M. : Izvestia, 2011. - P. 180, Permutări aleatorii. - ISBN 978-5-206-00824-1 .
• I.V. Krasikov, I.E. Krasikov. Algoritmi. La fel ca doi și doi. - M . : Eksmo, 2007. - ISBN 978-5-699-21047-3 .
• B.N. Ivanov. Matematică discretă. Algoritmi si programe: Proc. indemnizatie. La fel ca doi și doi. - M .: Laboratory of Basic Knowledge, 2003. - P. 89. 4.8 Generarea de permutări aleatorii. - (Universitate tehnica). — ISBN 5-93208-093-0 .

Link -uri

• Permutare aleatorie la MathWorld
• Generare aleatorie de permutare - o prezentare detaliată a algoritmului de amestecare al lui Knuth și a variantelor sale pentru generarea de permutări ale k -permutărilor (permutări ale k elemente selectate dintr-o listă) și k - submulțimi
• Gherasimov Vasili Alexandrovici. Generarea de combinații aleatorii. Generarea unei combinații după numărul său ordinal. Revista RSDN #3-2010