Satunnainen permutaatio

Satunnaispermutaatio  on objektijoukon satunnainen järjestys eli satunnaismuuttuja, jonka alkeistapahtumat ovat permutaatioita . Satunnaispermutaatioiden käyttö on usein perusta satunnaistettuja algoritmeja käyttävillä aloilla . Tällaisia ​​aloja ovat koodausteoria , kryptografia ja mallintaminen . Hyvä esimerkki satunnaisesta permutaatiosta on korttipakan sekoittaminen .

Luodaan satunnaisia ​​permutaatioita

Suora menetelmä (elementti kerrallaan)

Eräs menetelmä n elementin joukon satunnaispermutaatioiden generoimiseksi on käyttää tasaista jakaumaa , joka valitsee peräkkäin satunnaisluvut väliltä 1 ja n varmistaen samalla, että toistoja ei esiinny. Tuloksena oleva sekvenssi ( x 1 , …, x n ) tulkitaan permutaatioksi

Suora generointimenetelmä edellyttää satunnaisluvun valinnan toistamista, jos arvottu numero on jo järjestyksessä. Tämä voidaan välttää, jos i - vaiheessa (kun x 1 , …, x i - 1 on jo valittu) valitaan satunnaisluku j väliltä 1 ja n - i + 1 ja valitaan sitten x i yhtä kuin j :s valitsematon luku.

Whip Shuffling

Yksinkertainen algoritmi n elementin (tasaisesti jakautuneen) satunnaisten permutaatioiden luomiseksi ilman toistoja, joka tunnetaan nimellä Knuth shuffling , alkaa mielivaltaisella permutaatiolla (esim. identtisellä permutaatiolla ilman elementtien permutaatiota) ja siirtyy paikasta 1 paikkaan n − 1, elementin permutointi paikoilla i satunnaisesti valitulla elementillä paikoissa i - n mukaan lukien. On helppo osoittaa, että tällä tavalla saamme kaikki n alkion permutaatiot todennäköisyydellä täsmälleen 1/ n !.

Tilastot satunnaisista permutaatioista

Kiinteät kohdat

Kiinteiden pisteiden lukumäärän todennäköisyysjakauma tasaisesti jakautuneissa satunnaisissa permutaatioissa n elementillä lähestyy Poissonin lakia n kasvaessa . Kiinteiden pisteiden laskeminen on klassinen esimerkki inkluusio-poissulkemiskaavan käytöstä , joka osoittaa, että todennäköisyys, että kiinteitä pisteitä ei ole, lähestyy 1/ e . Tässä tapauksessa kiinteiden pisteiden lukumäärän matemaattinen odotus on yhtä suuri kuin 1 mille tahansa permutaatiokoolle. [yksi]

Satunnaisuustesti

Kuten kaikkien satunnaisprosessien kohdalla, permutaatioiden generointialgoritmin, erityisesti Knuthin sekoitusalgoritmin, laatu riippuu taustalla olevasta satunnaislukugeneraattorista, kuten näennäissatunnaislukugeneraattorista . On olemassa suuri määrä mahdollisia satunnaisuustestejä , kuten diehard-testejä . Tyypillinen esimerkki tällaisesta testistä on valita jokin tilasto, jonka jakauma tunnetaan, ja tarkistaa, onko tämän tilaston jakauma saadulle permutaatiojoukolle riittävän lähellä todellista jakaumaa.

Katso myös

• Golomb-Dickman vakio
• Sekoitusalgoritmit  - satunnaislajittelumenetelmä, iteratiivinen permutaatiomenetelmä
• satunnainen permutaatio
• Kryptaanalyysi LEX
• 100 vangin ja 100 laatikon ongelma

Muistiinpanot

1. ↑ D. Knuth, R. Graham, O. Patashnik. konkreettista matematiikkaa. - Maailma, 1998.

Kirjallisuus

• Jim Pitman. Todennäköisyys. — Springer Science & Business Media, 2012. — S. 153–. - ISBN 978-1-4612-4374-8 .
• VG Potemkin “MATLAB Handbook” Työskentely harvoilla matriiseilla. Kuvataan randperm-proseduurin käyttö satunnaisten permutaatioiden luomiseen MathLab-paketissa.
• Alfred W. Aho, John Hopcroft, Jeffrey D. Ullman. Tietorakenteet ja algoritmit. - Kustantaja "Williams", 2003. - S. 129-130. - ISBN 0-201-00023-7 / 5-8459-0122-7.
• Alfred W Aho, John E Hopcroft, Jeffrey D Ullman. Algoritmit. Rakentaminen ja analyysi. - Pietari, Moskova, Kiova: Williams Publishing House, 2007. - S. 152-153 Luku 5. Todennäköisyysanalyysi ja satunnaistetut algoritmit.
• Arnold V.I. Matemaattisten tosiasioiden kokeellinen havainnointi . - M .: MTSNMO, 2006. - S.  66 -84. — (Kesäkoulu "Moderni matematiikka"). - ISBN 978-5-94057-282-4 .
• T. Christiansen, N. Torkington. perl. Ohjelmoijan kirjasto. - Peter, 2001. - S. Luku 4 "Matriisit" kattaa kaiken, mikä liittyy toimintoihin listoilla ja taulukoilla, mukaan lukien yksilöllisten elementtien löytäminen, tehokas lajittelu ja elementtien satunnainen permutaatio .. - ISBN 5-8046-0094-X .
• Kormen T., Leyzerson Ch., Rivest R., Stein K. Algoritmit: rakentaminen ja analyysi. - M. : "Williams", 2005. - S. Luku 5.3 Satunnaistetut algoritmit. — ISBN 5-8459-0857-4 .
• Boris Nikolajevitš Ivanov. Diskreetti matematiikka. Algoritmit ja ohjelmat. Jatkokurssi. - M. : Izvestia, 2011. - P. 180, Satunnaiset permutaatiot. - ISBN 978-5-206-00824-1 .
• I.V. Krasikov, I.E. Krasikov. Algoritmit. Aivan kuten kaksi ja kaksi. - M . : Eksmo, 2007. - ISBN 978-5-699-21047-3 .
• B.N. Ivanov. Diskreetti matematiikka. Algoritmit ja ohjelmat: Proc. korvaus. Aivan kuten kaksi ja kaksi. - M .: Laboratory of Basic Knowledge, 2003. - S. 89. 4.8 Satunnaispermutaatioiden generointi. - (Teknillinen yliopisto). — ISBN 5-93208-093-0 .

Linkit

• Satunnainen permutaatio MathWorldissä
• Satunnaisten permutaatioiden generointi - yksityiskohtainen esitys Knuthin sekoitusalgoritmista ja sen muunnelmista k -permutaatioiden ( luettelosta valitun k elementin permutaatioiden) ja k - osajoukon permutaatioiden generoimiseksi
• Gerasimov Vasili Aleksandrovitš. Satunnaisten yhdistelmien luominen. Yhdistelmän luominen sen järjestysnumerolla. RSDN-lehti #3-2010