Véletlenszerű permutáció

A véletlenszerű permutáció objektumok  halmazának véletlenszerű sorrendje, azaz olyan valószínűségi változó , amelynek elemi eseményei permutációk . A véletlenszerű permutációk használata gyakran az alap a véletlenszerű algoritmusokat használó mezőkben . Ilyen területek a kódoláselmélet , a kriptográfia és a modellezés . A véletlenszerű permutáció jó példája a kártyapakli megkeverése .

Véletlenszerű permutációk generálása

Közvetlen metódus (elemről elemre)

Az egyik módszer n elemből álló halmaz véletlenszerű permutációjának generálására az , hogy egyenletes eloszlást használunk, amely 1 és n közötti szekvenciális véletlen számokat választ ki , miközben biztosítja, hogy ne legyenek ismétlődések. Az így kapott sorozatot ( x 1 , …, x n ) permutációként értelmezzük

A közvetlen generálási módszer megköveteli egy véletlen szám kiválasztásának megismétlését, ha a kihúzott szám már a sorozatban van. Ez elkerülhető, ha az i - edik lépésben (amikor x 1 , …, x i - 1 már ki van választva) választunk egy j véletlenszámot 1 és n - i + 1 között, majd kiválasztjuk, hogy x i egyenlő a j -edik nem választott szám.

Whip Shuffling

Egy egyszerű algoritmus n elem véletlenszerű permutációjának (egyenletes eloszlású) generálására ismétlődés nélkül, Knuth shuffling néven ismert , tetszőleges permutációval kezdődik (például azonos permutációval az elemek permutációja nélkül), és az 1-es pozícióból az n -1- es pozícióba lép. az elem permutálása i pozíciókkal egy véletlenszerűen kiválasztott elemmel az i -től n - ig terjedő pozíciókban. Könnyen kimutatható, hogy így n elem összes permutációját pontosan 1/ n ! valószínűséggel kapjuk meg.

Statisztikák véletlenszerű permutációkról

Rögzített pontok

A fix pontok számának valószínűségi eloszlása ​​egyenletes eloszlású véletlenszerű permutációkban n elemen közelíti a Poisson-törvényt n növekedésével . A fix pontok számának számlálása a befogadás-kizárás formula használatának klasszikus példája , amely azt mutatja, hogy a fix pontok hiányának valószínűsége megközelíti az 1/ e -t . Ebben az esetben a fix pontok számának matematikai elvárása 1-gyel egyenlő a permutáció bármely méretére. [egy]

Véletlenszerűségi teszt

Mint minden véletlenszerű folyamat esetében, a permutációgeneráló algoritmusok minősége, különösen a Knuth-féle keverőalgoritmus, a mögöttes véletlenszám-generátortól, például az álvéletlenszám- generátortól függ . Számos lehetséges véletlenszerűségi teszt létezik , mint például a kemény tesztek . Egy ilyen teszt tipikus példája az, hogy olyan statisztikát választunk, amelynek eloszlása ​​ismert, és ellenőrizzük, hogy ennek a statisztikának a megoszlása ​​a kapott permutációk halmazán elég közel van-e a valós eloszláshoz.

Lásd még

• Golomb-Dickman állandó
• Keverő algoritmusok  - véletlenszerű rendezési módszer, iteratív permutációs módszer
• véletlenszerű permutáció
• Kriptanalízis LEX
• 100 fogoly és 100 doboz problémája

Jegyzetek

1. ↑ D. Knuth, R. Graham, O. Patashnik. konkrét matematika. - Világ, 1998.

Irodalom

• Jim Pitman. Valószínűség. — Springer Science & Business Media, 2012. — P. 153–. - ISBN 978-1-4612-4374-8 .
• VG Potemkin „MATLAB kézikönyv” Ritka mátrixokkal való munka. Leírjuk a randperm eljárás használatát véletlen permutációk generálására a MathLab csomagban.
• Alfred W. Aho, John Hopcroft, Jeffrey D. Ullman. Adatstruktúrák és algoritmusok. - "Williams" kiadó, 2003. - S. 129-130. - ISBN 0-201-00023-7 / 5-8459-0122-7.
• Alfred W Aho, John E Hopcroft, Jeffrey D Ullman. Algoritmusok. Építés és elemzés. - St. Petersburg, Moszkva, Kijev: Williams Publishing House, 2007. - P. 152-153 5. fejezet Valószínűségi elemzés és randomizált algoritmusok.
• Arnold V.I. Matematikai tények kísérleti megfigyelése . - M. : MTSNMO, 2006. - S.  66 -84. — (Modern matematika nyári iskola). - ISBN 978-5-94057-282-4 .
• T. Christiansen, N. Torkington. perl. Programozói könyvtár. - Peter, 2001. - S. A 4. "Tömbök" fejezet mindent lefed, ami a listákkal és tömbökkel kapcsolatos műveletekkel kapcsolatos, beleértve az egyedi elemek megtalálását, a hatékony rendezést és az elemek véletlenszerű permutációját .. - ISBN 5-8046-0094-X .
• Kormen T., Leyzerson Ch., Rivest R., Stein K. Algoritmusok: konstrukció és elemzés. - M. : "Williams", 2005. - S. 5.3. fejezet Véletlenszerű algoritmusok. — ISBN 5-8459-0857-4 .
• Borisz Nyikolajevics Ivanov. Diszkrét matematika. Algoritmusok és programok. Haladó tanfolyam. - M. : Izvesztyija, 2011. - P. 180, Véletlenszerű permutációk. - ISBN 978-5-206-00824-1 .
• I.V. Krasikov, I.E. Krasikov. Algoritmusok. Akárcsak kettő és kettő. - M . : Eksmo, 2007. - ISBN 978-5-699-21047-3 .
• B.N. Ivanov. Diszkrét matematika. Algoritmusok és programok: Proc. juttatás. Akárcsak kettő és kettő. - M .: Alapismeretek Laboratóriuma, 2003. - P. 89. 4.8 Véletlenszerű permutációk generálása. - (Technikai Egyetem). — ISBN 5-93208-093-0 .

Linkek

• Véletlenszerű permutáció a MathWorldben
• Véletlenszerű permutáció generálása - a Knuth-féle keverőalgoritmus és változatainak részletes bemutatása k -permutációk ( listából kiválasztott k elem permutációi) és k - részhalmazok permutációinak generálására
• Geraszimov Vaszilij Alekszandrovics. Véletlenszerű kombinációk generálása. Kombináció generálása a sorszám alapján. RSDN Magazine #3-2010