Fisher-Yates Shuffle (opkaldt efter Ronald Fisher og Frank Yates , også kendt som Knuth Shuffle (efter Donald Knuth ), er en algoritme til at generere tilfældige permutationer af et endeligt sæt , forenklet sagt, til tilfældig blanding af et sæt. En variant af Fisher- Yates-shuffling, kendt som Sattolo-algoritmen , kan bruges til at generere en tilfældig cyklus af permutationer af længden n . En korrekt implementeret Fisher-Yates-shuffle-algoritme er upartisk , så hver permutation genereres med samme sandsynlighed. Den aktuelle version af Algoritmen er meget effektiv og tager tid proportionalt med antallet af elementer i sættet og kræver ikke yderligere hukommelse.
Den grundlæggende procedure for Fisher-Yates shuffling ligner tilfældigt at trække sedler med tal fra en hat eller kort fra et spil, det ene element efter det andet, indtil elementerne løber tør. Algoritmen giver en effektiv og stringent metode til sådanne operationer, der garanterer et objektivt resultat.
Fisher-Yates shuffle, i sin oprindelige form, blev beskrevet i 1938 af Ronald Fisher og Frank Yates i deres bog Statistical Tables for Research in Biology, Architecture, and Medicine [1] (Den seneste udgave af bogen beskriver en anden blandealgoritme tilskrevet C. R. Rao .) Deres metode blev udviklet til blyant og papir og brugte forudberegnet tabeller med tilfældige tal som en kilde til tilfældighed. Det så sådan her ud:
Hvis tallene brugt i trin 2 faktisk er tilfældige og ikke biased, så får vi de samme tilfældige permutationer (tilfældige og ikke biased). Fisher og Yates beskrev, hvordan man får sådanne tilfældige tal for ethvert interval og angav tabeller for at undgå bias. De forestillede sig også muligheden for at forenkle metoden - at vælge tilfældige tal fra et til N og derefter kassere gentagelser - for at generere halvdelen af den genererede permutation, og først derefter bruge en mere kompleks algoritme for den resterende halvdel, ellers vil gentagne tal også komme på tværs tit.
En moderne version af Fisher-Yates shuffle-algoritmen til brug i computere blev præsenteret af Richard Durstenfeld i 1964 i Communications of the ACM Volume 7, Issue 7, med titlen "Algorithm 235: Random permutation" [2] , og blev populariseret af Donald Knuth i andet bind af hans bog The Art of Programming as Algorithm P [3] . Hverken Durstenfeld eller Knuth nævnte Fisher og Yates' algoritme i den første udgave af bogen og ser ud til at have været uvidende om det. I anden udgave af The Art of Programming blev denne udeladelse imidlertid rettet [4]
Algoritmen beskrevet af Durstenfeld adskiller sig fra Fisher og Yates algoritmen i små, men væsentlige detaljer. For at forhindre computerimplementeringen af algoritmen i at spilde tid på at gentage de resterende numre i trin 3, blev Durstenfelds valgte numre overført til slutningen af listen ved hver iteration ved at permutere med det sidste fravalgte tal. Denne modifikation reducerede tidskompleksiteten af algoritmen til O ( n ), sammenlignet med O ( n 2 ) for den originale algoritme [5] . Denne ændring fører til følgende algoritme.
For at blande et array a med n elementer (indeks 0..n-1): for alle i fra n − 1 til 1 , udfør j ← tilfældigt tal 0 ≤ j ≤ i skift a [ j ] og a [ i ]Fischer-Yates shuffle i Durstenfeld varianten er en shuffle på plads . Det vil sige, at når den får et fyldt array, blander det elementerne i det samme array i stedet for at skabe en kopi af arrayet med elementerne omarrangeret. Dette kan give en betydelig fordel, når du blander store arrays.
Initialisering og blanding af et array på samme tid kan øge effektiviteten en smule, hvis du bruger den "omvendte" version af shufflen. I denne version flyttes det originale element ved indeks i til en tilfældig position blandt de første i - positioner, efter at elementet er flyttet fra denne position til position i . I tilfælde af at vælge et tilfældigt tal lig med i , vil den ikke-tildelte værdi først blive overført, men den vil straks blive overskrevet af den korrekte værdi. Ingen separat initialisering er nødvendig i denne variant, og der udføres ingen permutationer. Hvis kilden er defineret af en simpel funktion, såsom heltal fra 0 til n - 1 , kan kilden blot erstattes af den funktion, da kilden aldrig ændres under kørselstid.
Sådan oprettes en matrix a fra n tilfældigt blandede kildeelementer : for i fra 0 til n − 1 do j ← tilfældigt heltal med 0 ≤ j ≤ i a [ i ] ← a [ j ] a [ j ] ← kilde [ i ]Rigtigheden af den "omvendte" shuffle kan bevises ved induktion; nogen af n ! forskellige sekvenser af tilfældige tal opnået under driften af algoritmen danner sin egen permutation, således at alle permutationer kun modtages én gang.
En anden fordel ved denne tilgang er, at uden at kende tallet "n", antallet af elementer i kilden , kan vi skabe ensartet fordelte permutationer. Under array a oprettes iterativt startende fra tom, og en .length repræsenterer dens aktuelle længde.
mens kilde .iselther j ← tilfældigt tal 0 ≤ j ≤ a .længde hvis j = a .længde a .add( source .nextItem) ellers a .add( a [ j ]) a [ j ] ← source .nextItemLad os som et eksempel omarrangere tallene fra 1 til 8 ved hjælp af den originale Fisher-Yates-metode . Lad os først skrive tallene på papir:
| Interval | Valgte | Udkast | Resultat |
|---|---|---|---|
| 1 2 3 4 5 6 7 8 |
Lad os nu tage et tilfældigt tal k fra 1 til 8 - lad det være 3 - og krydse det kth (det vil sige det tredje) tal (3, selvfølgelig) ud og overføre det til den resulterende sekvens:
| Interval | Valgte | Udkast | Resultat |
|---|---|---|---|
| 1-8 | 3 | 1 2 3 4 5 6 7 8 | 3 |
Nu vælger vi et andet tilfældigt tal, denne gang fra intervallet 1-7, lad det være 4. Nu overstreger vi det fjerde tal , der endnu ikke er streget over fra kladden - det bliver tallet 5 - og tilføjer det til resultatet:
| Interval | Valgte | Udkast | Resultat |
|---|---|---|---|
| 1-7 | fire | 1 2 3 4 5 6 7 8 | 3 5 |
Nu vælger vi et tilfældigt tal fra intervallet 1-6, derefter fra intervallet 1-5, og så videre, og gentager processen med at overstrege som beskrevet ovenfor:
| Interval | Valgte | Udkast | Resultat |
|---|---|---|---|
| 1-6 | 5 | 1 2 3 4 5 6 7 8 | 3 5 7 |
| 1-5 | 3 | 1 2 3 4 5 6 7 8 | 3 5 7 4 |
| 1-4 | fire | 1 2 3 4 5 6 7 8 | 3 5 7 4 8 |
| 1-3 | en | 1 2 3 4 5 6 7 8 | 3 5 7 4 8 1 |
| 1-2 | 2 | 1 2 3 4 5 6 7 8 | 3 5 7 4 8 1 6 |
| 1 2 3 4 5 6 7 8 | 3 5 7 4 8 1 6 2 |
Lad os gøre det samme med Durstenfeld-metoden . Denne gang, i stedet for at strege de valgte numre over og kopiere dem et sted, omarrangerer vi dem med de numre, der endnu ikke er valgt. Som før starter vi med at skrive tal fra 1 til 8 ud:
| Interval | Valgte | Udkast | Resultat |
|---|---|---|---|
| 1 2 3 4 5 6 7 8 |
Lad os vælge det første tilfældige tal fra 1 til 8, lad os sige, at det er 6, så skift det 6. og 8. tal på listen:
| Interval | Valgte | Udkast | Resultat |
|---|---|---|---|
| 1-8 | 6 | 1 2 3 4 5 8 7 | 6 |
Vi vælger det næste tilfældige tal fra intervallet 1 - 7, og lader det være 2. Nu bytter vi 2. og 7. tal:
| Interval | Valgte | Udkast | Resultat |
|---|---|---|---|
| 1-7 | 2 | 1 7 3 4 5 8 | 26 _ |
Vi vælger det næste tilfældige tal fra intervallet 1 - 6, og lader det være 6, hvilket betyder, at vi skal lade det 6. tal være på plads (efter de foregående permutationer er tallet 8 her). Vi fortsætter med at handle på denne måde, indtil hele permutationen er dannet:
| Interval | Valgte | Udkast | Resultat |
|---|---|---|---|
| 1-6 | 6 | 1 7 3 4 5 | 8 2 6 |
| 1-5 | en | 5 7 3 4 | 1 8 2 6 |
| 1-4 | 3 | 5 7 4 | 3 1 8 2 6 |
| 1-3 | 3 | 5 7 | 4 3 1 8 2 6 |
| 1-2 | en | 7 | 5 4 3 1 8 2 6 |
En meget lignende algoritme blev udgivet i 1986 af Sandra Sattolo for at generere ensartet fordelte cyklusser af (maksimal) længde n [6] Forskellen mellem Durstenfeld og Sattolo algoritmerne er kun i trin 2 - i Sattolos algoritme vælges et tilfældigt tal j fra intervallet 1 - i −1, ikke fra 1 - i . Denne simple modifikation resulterer i permutationer bestående af en enkelt cyklus.
Faktisk, som beskrevet nedenfor, er det nemt ved et uheld at implementere Sattolo-algoritmen, når du forsøger at skabe Fisher-Yates-algoritmen. En sådan fejl fører til generering af permutationer fra et mindre sæt ( n − 1)! cyklusser af længde N , i stedet for et fuldt sæt af n ! mulige permutationer.
At Suttolos algoritme altid skaber en cyklus med længden n kan vises ved induktion. Antag, at efter den første iteration (som flyttede element n til − 1.− 1 iterationer en cyklus af elementer med længdenn, dannede de resterende)n<kposition Ifølge den accepterede antagelse vil vi kun komme til startpositionen ved at gennemgå alle de andre positioner. Det sidste element, efter flytning til position k , og successive permutationer af de første n − 1 elementer, vil ende i position l ; sammenlign permutationen π af alle n elementer med permutationen σ af de første n − 1 elementer. Ved at holde styr på permutationer som nævnt ovenfor, finder vi ikke forskellen mellem π og σ , før vi når position k . I π vil elementet i position k flytte til den sidste position, ikke positionen l , og elementet på positionen sidst vil gå til positionen l . Startende fra dette punkt vil sekvensen af bevægelser af elementerne π igen falde sammen med σ , og alle positioner vil blive krydset, før de vender tilbage til den oprindelige position, efter behov.
Som i tilfældet med at bevise ligesandsynligheden for permutationer, er det tilstrækkeligt at vise, at Sattolos algoritme skaber ( n − 1)! forskellige permutationer, der på grund af tilfældig talgeneratorens formodede upartiskhed har lige stor sandsynlighed. ( n −1)! forskellige permutationer genereret af algoritmen dækker nøjagtigt sættet af cyklusser af længden n .
En simpel Python -implementering af Sattolos algoritme :
fra random import randrange def sattoloCycle ( items ): i = len ( items ) mens i > 1 : i = i - 1 j = randrange ( i ) # 0 <= j <= i-1 items [ j ], items [ i ] = items [ i ], varer [ j ] returFisher-Yates-algoritmen er ret effektiv, og endnu mere er dens hastighed og hukommelsesomkostninger asymptotisk optimale. Når du bruger en uvildig tilfældig talgenerator af høj kvalitet, garanterer algoritmen et objektivt resultat. Algoritmen har endnu en fordel - hvis det er nødvendigt for at opnå en del af permutationerne, kan algoritmen stoppes halvvejs eller endda stoppes og genoptages mange gange.
Der er en alternativ metode - hvert element i sættet tildeles et tilfældigt tal, og derefter sorteres sættet efter de tildelte numre. Det asymptotiske hastighedsestimat for sortering er i bedste fald O ( n log n ) , hvilket er uforlignelig med O ( n ) hastighedsestimatet for Fisher-Yates algoritmen. Ligesom Fisher-Yates shuffle producerer sorteringsmetoden uvildige permutationer, men den er mindre følsom over for mulige problemer med tilfældig talgeneratoren. Dog bør man være særlig opmærksom på at generere tilfældige tal for at undgå gentagelse, da en sorteret algoritme generelt ikke sorterer elementer tilfældigt.
Der er en variant af sorteringsmetoden, hvor listen sorteres ved hjælp af en sammenligningsfunktion, der returnerer et tilfældigt tal. Dette er dog en usædvanlig dårlig metode : det er meget sandsynligt, at den danner en uensartet fordeling, derudover afhængig af den anvendte sorteringsmetode [7] [8] . For eksempel ved brug af quicksort , med et fast element brugt som startelement. Denne sorteringsalgoritme sammenligner de resterende elementer på listen med den valgte (mindre eller større end den), og på denne måde bestemmes elementets resulterende position. Hvis sammenligningen returnerer "mindre end" og "større end" med lige stor sandsynlighed, så vil det valgte element være i midten med en meget højere sandsynlighed end ved enderne. En anden sorteringsmetode, som merge sort , kan producere permutationer med en mere ensartet sandsynlighed, men har stadig ulemper, fordi sammenlægning af to sekvenser med et tilfældigt udvalg af en sekvens med samme sandsynlighed (indtil vi løber tør for en sekvens af tilfældige tal) producere et resultat med en ensartet sandsynlighedsfordeling, da sandsynligheden for at vælge en sekvens skal være proportional med antallet af elementer i sekvensen. Faktisk kan ingen "møntkast"-metode, dvs. konsekutiv udvælgelse af to muligheder, skabe permutationer (af mere end to elementer) med en ensartet fordeling, da enhver hændelse under denne ordning har en sandsynlighed i form af en rationel brøk med en divisor lig med potensen to, mens den nødvendige sandsynlighed skal være 1/ n !.
I princippet kan sådanne blandemetoder føre til en algoritmesløjfe eller hukommelsesadgangsfejl, da korrektheden af sorteringsalgoritmen kan afhænge af bestillingsegenskaber såsom transitivitet [9] . Selvom denne form for adfærd ikke bør ske i former, hvor sammenligningen ikke kan forudsiges ud fra tidligere sammenligninger, er der nogle gange grunde til sådanne sammenligninger. For eksempel kan det faktum, at et element af effektivitetens skyld altid skal være lig med sig selv, bruges som en form for tegn eller flag, og det bryder i tilfælde af tilfældige sammenligninger sorteringsalgoritmen.
Der skal udvises forsigtighed ved implementering af Fisher-Yates-algoritmen, både med hensyn til selve algoritmen og med hensyn til den tilfældige talgenerator, som den er baseret på. Nogle almindelige implementeringsfejl er angivet nedenfor.
En almindelig fejl i implementeringen af Fisher-Yates shuffle er at vælge tilfældige tal fra det forkerte interval [10] . En defekt algoritme kan se ud til at fungere korrekt, men den skaber ikke alle mulige permutationer med lige stor sandsynlighed, og nogle permutationer oprettes måske slet ikke. For eksempel kan der opstå en generel underestimerings- eller overestimeringsfejl af én , når man vælger indekset j for det element, der skal byttes i eksemplet ovenfor , altid er mindre end indekset i , som elementet skal byttes med. Som et resultat får vi i stedet for Fisher-Yates- shufflen Sattolo-algoritmen , som danner permutationer, der påvirker alle elementer. Især i dette tilfælde kan intet element være i udgangspositionen.
På samme måde danner valg af j fra alle indekserne i arrayet ved hver iteration også ikke-ækvivalente permutationer, dog ikke så indlysende. Dette kan konstateres ud fra det faktum, at en sådan implementering frembringer n n forskellige elementudvekslinger, mens der kun er n ! mulige permutationer af en række af n elementer. Fordi n n aldrig kan deles med n ! ingen rest for n > 2 (fordi n ! er delelig med n − 1, som ikke har nogen fælles primtal divisorer med n ), skal nogle permutationer forekomme oftere end andre. Overvej et specifikt eksempel på permutationer af tre elementer [1, 2, 3]. Der er 6 mulige permutationer af dette sæt (3! = 6), men algoritmen genererer 27 permutationer (3 3 = 27). I dette tilfælde forekommer [1, 2, 3], [3, 1, 2] og [3, 2, 1] 4 gange hver i 27 blandinger, mens de resterende 3 forekommer 5 gange hver.
Matricen til højre viser sandsynligheden for, at hvert element fra listen med længde 7 vises i den endelige position. Bemærk, at for de fleste elementer har det en minimumssandsynlighed at blive i deres oprindelige position (matrixens hoveddiagonal), mens du blander, og at flytte en position til venstre har en maksimal sandsynlighed.
Fisher-Yates-algoritmen bruger en stikprøve af ensartet fordelte tilfældige tal fra forskellige områder. De fleste generatorer af tilfældige tal , både ægte tilfældige og pseudo-tilfældige, giver tal i et fast område, f.eks. fra 0 til 2 32 −1. En simpel og almindeligt anvendt metode til at reducere sådanne tal til det ønskede interval er at bruge resten af divisionen med den øvre grænse. Behovet for at generere tilfældige tal i alle intervaller fra 0-1 til 0 - n sikrer, at nogle af disse grænser ikke deler generatorens naturlige grænse ligeligt. Som følge heraf vil fordelingen ikke være ensartet, og små rester vil forekomme hyppigere.
Antag for eksempel, at generatoren producerer tilfældige tal mellem 0 og 99 (som Fisher og Yates gjorde i deres originale regneark), og du vil have tilfældige tal mellem 0 og 15. Hvis du blot finder resten af et tal, når det divideres med 16 , vil du opdage, at tallene 0-3 forekommer 17 % oftere end resten. Grunden til dette er, at 16 ikke deler 100 ligeligt - det største multiplum af 16, der ikke overstiger 100, er 6x16 = 96, og de resterende tal i intervallet 96-99 skaber ujævnheder. Den nemmeste måde at undgå dette problem på er at kassere sådanne numre, før du tager resten. Selvom der i princippet kan forekomme tal fra et sådant interval, er den matematiske forventning om antallet af genforsøg altid mindre end én.
Et lignende problem opstår, når du bruger en tilfældig talgenerator, der producerer flydende kommatal , normalt i området [0,1). Det resulterende tal ganges med størrelsen af det ønskede område og rundes op. Problemet her er, at selv pænt genererede tilfældige flydende kommatal har en begrænset præcision, hvilket betyder, at man kun kan få et endeligt antal mulige flydende kommatal, og som i tilfældet ovenfor brydes disse tal op i segmenter, der ikke deler tallet. er heltal, og nogle segmenter har større sandsynlighed for at dukke op end andre.
Yderligere problemer opstår, når du bruger en pseudo-tilfældig talgenerator (PRNG). Generering af en pseudo-tilfældig sekvens af sådanne generatorer er fuldstændig bestemt af deres interne tilstand ved begyndelsen af genereringen. Et shuffle-program baseret på en sådan generator kan ikke skabe flere permutationer end antallet af interne tilstande i generatoren. Selv når antallet af mulige generatortilstande overlapper antallet af permutationer, kan nogle permutationer forekomme hyppigere end andre. For at undgå forekomsten af ujævn fordeling skal antallet af interne tilstande af tilfældig talgeneratoren overstige antallet af permutationer med flere størrelsesordener.
For eksempel bruger den indbyggede pseudo-tilfældige talgenerator, der findes i mange programmeringssprog og biblioteker, typisk et 32-bit tal til interne tilstande, hvilket betyder, at en sådan generator kun kan generere 232 forskellige tilfældige tal. Hvis en sådan generator skulle bruges til at blande et spil med 52 spillekort , kunne det generere en meget lille brøkdel af 52! ≈ 2225,6 mulige permutationer. En generator med mindre end 226 bits interne tilstande kan ikke generere alle permutationer af et spil med 52 spillekort. Det menes, at for at skabe en ensartet fordeling er der behov for en generator med mindst 250-bit tilstande.
Naturligvis kan ingen pseudo-tilfældige tal-generator skabe flere tilfældige sekvenser givet af forskellige initialdata end antallet af disse initiale data. Så en generator med 1024-bit interne tilstande, for hvilke der er givet 32-bit initiale parametre, kan kun skabe 232 forskellige permutationssekvenser. Du kan få flere permutationer ved at vælge nok tilfældige tal fra generatoren, før du bruger den i shuffle-algoritmen, men denne tilgang er meget ineffektiv - at prøve f.eks. 2 30 tilfældige tal, før du bruger sekvensen i shuffle-algoritmen, øger kun antallet af permutationer til 262 .
Et andet problem opstår, når man bruger en simpel lineær kongruentiel PRNG, når resten af divisionen bruges til at reducere intervallet af tilfældige tal, som nævnt ovenfor. Problemet her er, at de lavere bits af en lineær kongruent PRNG er mindre tilfældige sammenlignet med de højere bits - de lavere n bits har en periode på højst 2 n . Hvis divisor er en potens af to, betyder det at tage resten at kassere bits af høj orden, hvilket resulterer i en betydelig reduktion i tilfældighed.
Endelig skal det bemærkes, at selv ved brug af en fin generator, kan der opstå en fejl i algoritmen på grund af forkert brug af generatoren. Forestil dig for eksempel, at Java -implementeringen af algoritmen skaber en ny generator for hvert kald til shuffle-processen uden at indstille parametre i konstruktøren. Det aktuelle tidspunkt (System.currentTimeMillis()) vil blive brugt til at initialisere generatoren. Således vil to opkald med en tidsforskel på mindre end et millisekund give identiske permutationer. Dette vil næsten helt sikkert ske, hvis blandingen sker gentagne gange og hurtigt, hvilket resulterer i en meget ujævn fordeling af permutationer. Det samme problem kan opstå, når man modtager tilfældige tal fra to forskellige strømme. Det er mere korrekt at bruge en statisk forekomst af generatoren, defineret uden for shuffle-rutinen.