Slumpmässig permutation

En slumpmässig permutation  är en slumpmässig ordning av en uppsättning objekt, det vill säga en slumpvariabel vars elementära händelser är permutationer . Användningen av slumpmässiga permutationer är ofta grunden i fält som använder randomiserade algoritmer . Sådana områden inkluderar kodningsteori , kryptografi och modellering . Ett bra exempel på en slumpmässig permutation är att blanda en kortlek .

Genererar slumpmässiga permutationer

Direkt metod (element för element)

En metod för att generera en slumpmässig permutation av en uppsättning av n element är att använda en enhetlig fördelning , som väljer sekventiellt slumpmässiga tal mellan 1 och n , samtidigt som man säkerställer att det inte finns några upprepningar. Den resulterande sekvensen ( x 1 , …, xn ) tolkas som en permutation

Den direkta genereringsmetoden kräver att man upprepar valet av ett slumpmässigt tal om det dragna numret redan finns i sekvensen. Detta kan undvikas om, i det i -te steget (när x 1 , …, x i - 1 redan är vald), väljer ett slumpmässigt tal j mellan 1 och n - i + 1 och sedan väljer x i lika med det j -te ovalda numret.

Whip Shuffling

En enkel algoritm för att generera slumpmässiga permutationer av n element (jämnt fördelade) utan upprepningar, känd som Knuth shuffling , börjar med en godtycklig permutation (t.ex. den identiska permutationen utan att permutera elementen), och går från position 1 till position n − 1, permutering av elementet med positionerna i med ett slumpmässigt valt element vid positionerna i till och med n . Det är lätt att visa att vi på detta sätt får alla permutationer av n element med en sannolikhet på exakt 1/ n !.

Statistik över slumpmässiga permutationer

Fasta punkter

Sannolikhetsfördelningen av antalet fixpunkter i likformigt fördelade slumpmässiga permutationer på n element närmar sig Poissons lag när n växer . Att räkna antalet fasta punkter är ett klassiskt exempel på att använda inklusions-exkluderingsformeln , som visar att sannolikheten för inga fixpunkter närmar sig 1/ e . I det här fallet är den matematiska förväntan av antalet fasta punkter lika med 1 för varje storlek på permutationen. [ett]

Slumpmässighetstest

Som med alla slumpmässiga processer beror kvaliteten på en permutationsgenereringsalgoritm, i synnerhet Knuths shufflingalgoritm, på den underliggande slumptalsgeneratorn, såsom pseudoslumptalsgeneratorn . Det finns ett stort antal möjliga slumpmässiga tester , såsom diehard-tester . Ett typiskt exempel på ett sådant test är att välja någon statistik för vilken fördelningen är känd, och kontrollera om fördelningen av denna statistik på uppsättningen av erhållna permutationer är tillräckligt nära den verkliga fördelningen.

Se även

• Golomb-Dickman konstant
• Blandningsalgoritmer  - slumpmässig sorteringsmetod, iterativ permutationsmetod
• slumpmässig permutation
• Kryptanalys LEX
• Problemet med 100 fångar och 100 lådor

Anteckningar

1. ↑ D. Knuth, R. Graham, O. Patashnik. konkret matematik. - Världen, 1998.

Litteratur

• Jim Pitman. Sannolikhet. — Springer Science & Business Media, 2012. — S. 153–. - ISBN 978-1-4612-4374-8 .
• VG Potemkin “MATLAB Handbook” Arbeta med glesa matriser. Användningen av randperm-proceduren för att generera slumpmässiga permutationer i MathLab-paketet beskrivs.
• Alfred W. Aho, John Hopcroft, Jeffrey D. Ullman. Datastrukturer och algoritmer. - Förlaget "Williams", 2003. - S. 129-130. - ISBN 0-201-00023-7 / 5-8459-0122-7.
• Alfred W Aho, John E Hopcroft, Jeffrey D Ullman. Algoritmer. Konstruktion och analys. - St. Petersburg, Moskva, Kiev: Williams Publishing House, 2007. - S. 152-153 Kapitel 5. Probabilistisk analys och randomiserade algoritmer.
• Arnold V.I. Experimentell observation av matematiska fakta . - M. : MTSNMO, 2006. - S.  66 -84. — (Sommarskola "Modern matematik"). - ISBN 978-5-94057-282-4 .
• T. Christiansen, N. Torkington. perl. Programmerarens bibliotek. - Peter, 2001. - S. Kapitel 4 "Arrayer" täcker allt relaterat till operationer med listor och arrayer, inklusive att hitta unika element, effektiv sortering och slumpmässig permutation av element .. - ISBN 5-8046-0094-X .
• Kormen T., Leyzerson Ch., Rivest R., Stein K. Algoritmer: konstruktion och analys. - M. : "Williams", 2005. - S. Kapitel 5.3 Randomiserade algoritmer. — ISBN 5-8459-0857-4 .
• Boris Nikolaevich Ivanov. Diskret matematik. Algoritmer och program. Avancerad kurs. - M. : Izvestia, 2011. - P. 180, Random permutations. - ISBN 978-5-206-00824-1 .
• I.V. Krasikov, I.E. Krasikov. Algoritmer. Precis som två och två. - M . : Eksmo, 2007. - ISBN 978-5-699-21047-3 .
• B.N. Ivanov. Diskret matematik. Algoritmer och program: Proc. ersättning. Precis som två och två. - M .: Laboratory of Basic Knowledge, 2003. - S. 89. 4.8 Generering av slumpmässiga permutationer. - (Tekniskt universitet). — ISBN 5-93208-093-0 .

Länkar

• Slumpmässig permutation på MathWorld
• Generering av slumpmässig permutation - en detaljerad presentation av Knuths blandningsalgoritm och dess varianter för att generera permutationer av k -permutationer (permutationer av k element valda från en lista) och k - delmängder
• Gerasimov Vasily Alexandrovich. Generering av slumpmässiga kombinationer. Generering av en kombination av dess ordningsnummer. RSDN Magazine #3-2010