A Fisher-Yates Shuffle ( Ronald Fisherről és Frank Yatesről nevezték el , más néven Knuth Shuffle ( Donald Knuth után )) egy véges halmaz véletlenszerű permutációinak generálására szolgáló algoritmus , egyszerűen fogalmazva egy halmaz véletlenszerű keverésére . A Sattolo-algoritmusként ismert Yates -keverés n hosszúságú permutációk véletlenszerű ciklusának generálására használható . A megfelelően megvalósított Fisher-Yates keverési algoritmus torzítatlan , így minden permutáció azonos valószínűséggel jön létre. A jelenlegi verzió Az algoritmus nagyon hatékony, és a halmaz elemeinek számával arányos időt vesz igénybe, és nem igényel további memóriát.
A Fisher-Yates keverés alapvető eljárása hasonló ahhoz, hogy véletlenszerűen húzza ki a kalapból a számjegyeket vagy a kártyákat a pakliból, egyik elemet a másik után, amíg az elemek el nem fogynak. Az algoritmus hatékony és szigorú módszert biztosít az ilyen műveletekhez, garantálva az elfogulatlan eredményt.
A Fisher-Yates keverést eredeti formájában 1938-ban Ronald Fisher és Frank Yates írta le Statisztikai táblázatok a biológia, építészet és orvostudomány kutatásához című könyvében [1] (a könyv legújabb kiadása egy másik keverési algoritmust ír le. C. R. Rao -nak tulajdonították .) Módszerüket ceruzára és papírra fejlesztették ki, és a véletlenszámok előre kiszámított táblázatait használták a véletlenszerűség forrásaként. Így nézett ki:
Ha a 2. lépésben használt számok valóban véletlenszerűek és nem torzítottak, akkor ugyanazokat a véletlenszerű permutációkat kapjuk (véletlenszerű és nem torzított). Fisher és Yates leírták, hogyan lehet ilyen véletlen számokat szerezni bármely intervallumhoz, és táblázatokat szolgáltattak a torzítás elkerülése érdekében. Elképzelték azt a lehetőséget is, hogy a módszer egyszerűsítésével - véletlen számok kiválasztásával egytől N -ig , majd az ismétlődések elvetésével - a generált permutáció felét generálják, és csak ezután alkalmazzanak bonyolultabb algoritmust a fennmaradó felére, különben ismétlődő számok is előfordulnak. gyakran.
A Fisher-Yates shuffle algoritmus számítógépekben használható modern változatát Richard Durstenfeld mutatta be 1964-ben a Communications of the ACM 7. kötet 7. számában, "Algoritmus 235: Random permutation" [2] címmel, és Donald Knuth népszerűsítette . a The Art of Programming as Algorithm P [3] című könyvének második kötetében . Sem Durstenfeld, sem Knuth nem említette Fisher és Yates algoritmusát a könyv első kiadásában, és úgy tűnik, nem is tudtak róla. A The Art of Programming második kiadásában azonban ezt a hiányosságot kijavították [4]
A Durstenfeld által leírt algoritmus apró, de jelentős részletekben különbözik a Fisher és Yates algoritmustól. Annak érdekében, hogy az algoritmus számítógépes megvalósítása ne vesztegessen időt a fennmaradó számok iterálására a 3. lépésben, a Durstenfeld által kiválasztott számok minden iterációnál átkerültek a lista végére, az utolsó ki nem választott számmal permutálva. Ez a módosítás O ( n )-ra csökkentette az algoritmus időbonyolultságát , összehasonlítva az eredeti algoritmus O ( n2 ) értékével [ 5 ] . Ez a változás a következő algoritmushoz vezet.
Egy n elemű a tömb (indexek 0..n-1) keveréséhez: minden i -re n − 1 -től 1 -ig hajtsa végre a j ← véletlenszám 0 ≤ j ≤ i cserét a [ j ] és a [ i ]A Fischer-Yates shuffle a Durstenfeld változatban egy keverés a helyén . Ez azt jelenti, hogy ha kitöltött tömböt kap, akkor az ugyanabban a tömbben lévő elemeket megkeveri, ahelyett, hogy másolatot készítene a tömbről az elemekkel átrendezve. Ez jelentős előnyt jelenthet nagy tömbök keverésekor.
Egy tömb egyidejű inicializálása és keverése némileg növelheti a hatékonyságot, ha a keverés "fordított" változatát használja. Ebben a változatban az i indexben lévő eredeti elem egy véletlenszerű pozícióba kerül az első i pozíciók közé, miután az elemet ebből a pozícióból az i pozícióba helyezték át . i -vel egyenlő véletlenszám kiválasztása esetén először a hozzá nem rendelt érték kerül átvitelre, de azt azonnal felülírja a megfelelő érték. Ebben a változatban nincs szükség külön inicializálásra, és nem történik permutáció. Ha a forrást egy egyszerű függvény határozza meg, például a 0 és n - 1 közötti egész számok , akkor a forrás egyszerűen lecserélhető ezzel a függvénnyel, mivel a forrás soha nem változik futás közben.
A tömb létrehozása n véletlenszerűen kevert forráselemből : i -re 0 -tól n -ig − 1 do j ← véletlenszerű egész szám 0 ≤ j ≤ i a [ i ] ← a [ j ] a [ j ] ← forrás [ i ]A "fordított" keverés helyessége indukcióval igazolható; bármelyik n ! Az algoritmus működése során kapott véletlen számok különböző sorozatai saját permutációt alkotnak, így az összes permutációt csak egyszer kapjuk meg.
Egy másik előnye ennek a megközelítésnek, hogy az "n" szám, a forrás elemszámának ismerete nélkül is egyenletes eloszlású permutációkat hozhatunk létre. Az a tömb alatt iteratív módon, üresből indulva jön létre, és a .length az aktuális hosszát jelenti.
míg forrás .iselther j ← véletlenszám 0 ≤ j ≤ a .length if j = a .length a .add( source .nextItem) egyébként a .add( a [ j ]) a [ j ] ← forrás .nextItemPéldaként rendezzük át a számokat 1-ről 8 -ra az eredeti Fisher-Yates módszerrel . Először is írjuk fel a számokat papírra:
| Intervallum | Kiválasztott | Piszkozat | Eredmény |
|---|---|---|---|
| 1 2 3 4 5 6 7 8 |
Most vegyünk egy k véletlenszerű számot 1-től 8-ig - legyen ez 3 -, és húzzuk ki a k- adik (vagyis a harmadik) számot (természetesen 3), és vigyük át a kapott sorozatba:
| Intervallum | Kiválasztott | Piszkozat | Eredmény |
|---|---|---|---|
| 1-8 | 3 | 1 2 3 4 5 6 7 8 | 3 |
Most kiválasztunk egy második véletlen számot, ezúttal az 1-7 intervallumból, legyen az 4. Most áthúzzuk a negyedik számot , amely még nem volt áthúzva a piszkozatból - ez lesz az 5-ös szám - és hozzáadjuk. az eredményre:
| Intervallum | Kiválasztott | Piszkozat | Eredmény |
|---|---|---|---|
| 1-7 | négy | 1 2 3 4 5 6 7 8 | 3 5 |
Most kiválasztunk egy véletlen számot az 1-6 intervallumból, majd az 1-5 intervallumból, és így tovább, megismételve a fent leírt áthúzási folyamatot:
| Intervallum | Kiválasztott | Piszkozat | Eredmény |
|---|---|---|---|
| 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 | négy | 1 2 3 4 5 6 7 8 | 3 5 7 4 8 |
| 1-3 | egy | 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 |
Tegyük ugyanezt a Durstenfeld-módszerrel is . Ezúttal ahelyett, hogy áthúznánk a kiválasztott számokat és másolnánk valahova, átrendezzük a még ki nem választott számokkal. Mint korábban, kezdjük a számok kiírásával 1-től 8-ig:
| Intervallum | Kiválasztott | Piszkozat | Eredmény |
|---|---|---|---|
| 1 2 3 4 5 6 7 8 |
Válasszuk ki az első véletlen számot 1-től 8-ig, tegyük fel, hogy 6, tehát cserélje fel a 6. és 8. számot a listában:
| Intervallum | Kiválasztott | Piszkozat | Eredmény |
|---|---|---|---|
| 1-8 | 6 | 1 2 3 4 5 8 7 | 6 |
Kiválasztjuk a következő véletlen számot az 1-7 intervallumból, és legyen 2. Most felcseréljük a 2. és 7. számot:
| Intervallum | Kiválasztott | Piszkozat | Eredmény |
|---|---|---|---|
| 1-7 | 2 | 1 7 3 4 5 8 | 26 _ |
A következő véletlen számot az 1-6 intervallumból választjuk ki, és legyen 6, ami azt jelenti, hogy a 6. számot hagyjuk a helyén (az előző permutációk után itt a 8-as). Továbbra is így járunk el, amíg a teljes permutáció létre nem jön:
| Intervallum | Kiválasztott | Piszkozat | Eredmény |
|---|---|---|---|
| 1-6 | 6 | 1 7 3 4 5 | 8 2 6 |
| 1-5 | egy | 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 | egy | 7 | 5 4 3 1 8 2 6 |
Egy nagyon hasonló algoritmust 1986-ban publikált Sandra Sattolo egyenletes eloszlású (maximális) n hosszúságú ciklusok generálására [6] A Durstenfeld és Sattolo algoritmusok közötti különbség csak a 2. lépésben van – a Sattolo algoritmusában egy j véletlenszám kerül kiválasztásra. az 1 - i -1 intervallum, nem pedig 1 - i . Ez az egyszerű módosítás egyetlen ciklusból álló permutációkat eredményez.
Valójában az alábbiakban leírtak szerint könnyű véletlenül megvalósítani a Sattolo algoritmust, amikor megpróbáljuk létrehozni a Fisher-Yates algoritmust. Egy ilyen hiba egy kisebb halmazból ( n − 1) permutációkat generál! N hosszúságú ciklusok n teljes halmaza helyett ! lehetséges permutációk.
Az indukcióval kimutatható, hogy a Suttolo-algoritmus mindig n hosszúságú ciklust hoz létre . Tegyük fel, hogy az első iteráció után (amely az n elemet k < n pozícióba mozgatta ) a .1 hosszúságú elemciklust alkotott−niteráció1−nfennmaradó Az elfogadott feltevés szerint csak az összes többi pozíciót végigjárva jutunk el a kiindulási helyzethez. Az utolsó elem k pozícióba helyezése és az első n − 1 elem egymást követő permutációi után az l pozícióba kerül ; hasonlítsa össze az összes n elem π permutációját az első n − 1 elem σ permutációjával. A fent említett permutációk nyomon követésével nem találjuk meg a különbséget π és σ között, amíg el nem érjük a k pozíciót . π - ben a k pozícióban lévő elem az utolsó pozícióba kerül, nem az l pozícióba , és az utolsó pozícióban lévő elem az l pozícióba kerül . Ettől a ponttól kezdve a π elemek mozgási sorrendje ismét egybeesik σ -vel , és minden pozíciót bejárunk, mielőtt visszatérnénk a kiindulási helyzetbe, szükség szerint.
Csakúgy, mint a permutációk kiegyenlítődésének bizonyítása esetén, elég megmutatni, hogy a Sattolo-algoritmus létrehozza ( n − 1)! különböző permutációk, amelyek a véletlenszám-generátor feltételezett torzítatlansága miatt azonos valószínűséggel rendelkeznek. ( n −1)! Az algoritmus által generált különböző permutációk pontosan lefedik az n hosszúságú ciklusok halmazát .
A Sattolo algoritmus egyszerű Python implementációja :
véletlenszerű import randrange -ból def sattoCycle ( tételek ): i = len ( elemek ) míg i > 1 : i = i - 1 j = randrange ( i ) # 0 <= j <= i-1 tétel [ j ], tételek [ i ] = tételek [ i ], tételek [ j ] visszaA Fisher-Yates algoritmus meglehetősen hatékony, és még inkább a sebessége és a memóriaköltségei aszimptotikusan optimálisak. Kiváló minőségű, elfogulatlan véletlenszám-generátor használata esetén az algoritmus torzításmentes eredményt garantál. Az algoritmusnak van még egy előnye - ha a permutációk egy részét meg kell szerezni, akkor az algoritmus félúton leállítható, vagy akár többször is leállítható és folytatható.
Van egy alternatív módszer - a halmaz minden eleméhez véletlen számot rendelnek, majd a készletet a hozzárendelt számok szerint rendezik. A szortírozás aszimptotikus sebességbecslése legjobb esetben O ( n log n ) , ami összehasonlíthatatlan a Fisher-Yates algoritmus O ( n ) sebességbecslésével. A Fisher-Yates shuffle-hez hasonlóan a rendezési módszer is torzítatlan permutációkat eredményez, de kevésbé érzékeny a véletlenszám-generátor esetleges problémáira. Különös gondot kell azonban fordítani a véletlen számok generálására az ismétlődés elkerülése érdekében, mivel a rendezett algoritmus általában nem véletlenszerűen rendezi az elemeket.
A rendezési módszernek van egy változata, amelyben a lista egy véletlen számot visszaadó összehasonlító függvény segítségével rendezi. Ez azonban kivételesen rossz módszer : nagy valószínűséggel nem egyenletes eloszlást képez, ráadásul az alkalmazott válogatási módszertől függően [7] [8] . Például a quicksort használatakor egy rögzített elemet használva kezdőelemként. Ez a rendezési algoritmus összehasonlítja a lista többi elemét a kiválasztottal (ennél kisebb vagy nagyobb), és így meghatározza az elem eredő pozícióját. Ha az összehasonlítás egyenlő valószínűséggel adja vissza a "kisebb, mint" és a "nagyobb, mint" értéket, akkor a kiválasztott elem sokkal nagyobb valószínűséggel kerül a középpontba, mint a végén. Egy másik rendezési módszer, mint például az összevonási rendezés , egyenletesebb valószínűséggel hozhat létre permutációkat, de még mindig vannak hátrányai, mivel két sorozat összevonása egy sorozat véletlenszerű kiválasztásával azonos valószínűséggel (amíg ki nem fogy a véletlenszámokból álló sorozat) egyenletes valószínűség-eloszlású eredményt adunk, mivel a sorozatválasztás valószínűségének arányosnak kell lennie a sorozat elemeinek számával. Valójában egyetlen "érmefeldobási" módszer sem tud egyenletes eloszlású permutációt létrehozni (kétnél több elemből), mivel ebben a sémában minden eseménynek van egy racionális tört formájában való valószínűsége osztó egyenlő a kettes hatványával, míg a szükséges valószínűségnek 1/ n !-nek kell lennie.
Elvileg az ilyen keverési módszerek algoritmus hurokhoz vagy memória hozzáférési hibához vezethetnek, mivel a rendezési algoritmus helyessége függhet a rendezési tulajdonságoktól, például a tranzitivitástól [9] . Bár ez a fajta viselkedés nem fordulhat elő olyan fajtákban, ahol az összehasonlítás nem jelezhető előre a korábbi összehasonlítások alapján, néha okai vannak az ilyen összehasonlításoknak. Például az a tény, hogy egy elemnek mindig önmagával kell egyenlőnek lennie, a hatékonyság érdekében használható valamilyen jelként vagy zászlóként, és ez véletlenszerű összehasonlítások esetén sérti a rendezési algoritmust.
A Fisher-Yates algoritmus implementálásakor körültekintően kell eljárni, mind magát az algoritmust, mind az alapul szolgáló véletlenszám-generátort illetően. Az alábbiakban felsorolunk néhány gyakori megvalósítási hibát.
Gyakori hiba a Fisher-Yates shuffle megvalósításában, hogy véletlen számokat választanak ki rossz intervallumból [10] . Egy hibás algoritmus úgy tűnhet, hogy megfelelően működik, de nem hoz létre minden lehetséges permutációt egyenlő valószínűséggel, és előfordulhat, hogy egyes permutációk egyáltalán nem jönnek létre. Például általános alul- vagy túlbecslési hiba léphet fel, ha a fenti példában a cserélni kívánt elem j indexe mindig kisebb, mint az az i index , amellyel az elemet fel kell cserélni. Ennek eredményeként a Fisher-Yates shuffle helyett a Sattolo algoritmust kapjuk , amely minden elemet érintő permutációkat képez. Különösen ebben az esetben egyetlen elem sem lehet a kezdeti pozícióban.
Hasonlóképpen, ha a tömb összes indexéből j -t választunk minden iterációnál, szintén nem valószínű permutációkat képez, bár nem olyan nyilvánvaló. Ez abból a tényből állapítható meg, hogy egy ilyen megvalósítás n n különböző elemcserét produkál, miközben csak n ! n elemű tömb lehetséges permutációi . Mert n n soha nem osztható n -nel ! n > 2 esetén nincs maradék (mivel n ! osztható n − 1-gyel, aminek nincs közös prímosztója n -nel ), egyes permutációknak gyakrabban kell megjelenniük, mint másoknak. Tekintsünk egy konkrét példát három elem permutációjára [1, 2, 3]. Ennek a halmaznak 6 lehetséges permutációja van (3! = 6), de az algoritmus 27 permutációt generál (3 3 = 27). Ebben az esetben az [1, 2, 3], [3, 1, 2] és [3, 2, 1] 4-szer fordul elő 27 keverés során, míg a maradék 3 5-5 alkalommal.
A jobb oldali mátrix azt mutatja, hogy a 7 hosszúságú lista egyes elemei milyen valószínűséggel jelennek meg a végső pozícióban. Megjegyzendő, hogy a legtöbb elem esetében az eredeti pozícióban (a mátrix főátlójában) való tartásnak minimális a valószínűsége a keverés közben, és egy pozícióval balra való mozgásnak a legnagyobb a valószínűsége.
A Fisher-Yates algoritmus különböző tartományokból származó, egyenletes eloszlású véletlenszámokból álló mintát használ. A legtöbb véletlenszám-generátor azonban, mind a valódi véletlenszerű, mind az álvéletlen, fix tartományban ad számokat, mondjuk 0-tól 2-ig 32 −1. Egy egyszerű és általánosan használt módszer az ilyen számok kívánt intervallumra való csökkentésére az, hogy az osztás maradékát a felső korláttal használjuk. A véletlen számok generálása minden 0-1 és 0- n közötti intervallumban biztosítja, hogy ezen határok némelyike nem osztja egyenletesen a generátor természetes határát. Ennek eredményeként az eloszlás nem lesz egyenletes, és gyakrabban fordulnak elő kis maradékok.
Tegyük fel például, hogy a generátor 0 és 99 közötti véletlen számokat állít elő (ahogyan Fisher és Yates tette eredeti táblázataikban), és Ön 0 és 15 közötti véletlen számokat szeretne. , látni fogja, hogy a 0-3 számok 17%-kal gyakrabban fordulnak elő, mint a többi. Ennek az az oka, hogy a 16 nem osztja el egyenletesen a 100-at - a 16 legnagyobb többszöröse, amely nem haladja meg a 100-at, 6x16 = 96, a 96-99 tartományban lévő többi szám pedig egyenetlenséget okoz. A probléma elkerülésének legegyszerűbb módja, ha eldobja az ilyen számokat, mielőtt a maradékot megadná. Bár elvileg egy ilyen intervallumból származó számok is előfordulhatnak, az újrapróbálkozások számának matematikai elvárása mindig kisebb egynél.
Hasonló probléma lép fel olyan véletlenszám-generátor használatakor, amely lebegőpontos számokat állít elő , általában a [0,1 tartományban. A kapott számot megszorozzuk a kívánt tartomány méretével, és felfelé kerekítjük. A probléma itt az, hogy még a szépen generált véletlenszerű lebegőpontos számok is véges pontossággal rendelkeznek, ami azt jelenti, hogy csak véges számú lehetséges lebegőpontos számot kaphat, és mint a fenti esetben, ezek a számok szegmensekre bomlanak, amelyek nem osztják a számot. egész szám, és egyes szegmensek nagyobb valószínűséggel jelennek meg, mint mások.
További problémák merülnek fel pszeudo-véletlenszám-generátor (PRNG) használatakor. Az ilyen generátorok pszeudo-véletlen sorozatának létrehozását teljes mértékben meghatározza azok belső állapota a generálás elején. Egy ilyen generátoron alapuló keverőprogram nem tud több permutációt létrehozni, mint ahány a generátor belső állapota. Még akkor is, ha a lehetséges generátorállapotok száma átfedésben van a permutációk számával, egyes permutációk gyakrabban fordulhatnak elő, mint mások. Az egyenetlen eloszlás elkerülése érdekében a véletlenszám-generátor belső állapotainak számának több nagyságrenddel meg kell haladnia a permutációk számát.
Például a sok programozási nyelvben és könyvtárban megtalálható beépített pszeudo-véletlenszám-generátor jellemzően 32 bites számot használ a belső állapotokhoz, ami azt jelenti, hogy egy ilyen generátor csak 232 különböző véletlenszámot tud generálni. Ha egy ilyen generátort egy 52 kártyapakli megkeverésére használnának, az 52 -nek nagyon kis hányadát generálná ! ≈ 2225,6 lehetséges permutáció. A 226 bitnél kevesebb belső állapotú generátor nem tudja előállítani az 52 játékkártya pakli összes permutációját. Úgy gondolják, hogy az egységes eloszlás létrehozásához legalább 250 bites állapotú generátorra van szükség.
Természetesen egyetlen pszeudo-véletlenszám-generátor sem tud több olyan véletlenszerű sorozatot létrehozni, amely különböző kezdeti adatokkal adható meg, mint amennyi a kezdeti adatok száma. Tehát egy 1024 bites belső állapotú generátor, amelyhez 32 bites kezdeti paraméterek vannak megadva, csak 232 különböző permutációs sorozatot tud létrehozni. Több permutációt kaphat, ha elegendő véletlenszámot választ ki a generátorból, mielőtt azt a keverési algoritmusban használná, de ez a megközelítés nagyon nem hatékony - mondjuk 230 véletlen szám mintavétele a sorozat felhasználása előtt a keverési algoritmusban csak növeli a permutációk számát 2 62- re .
Egy másik probléma akkor merül fel, ha egy egyszerű lineáris kongruenciális PRNG-t használunk, amikor az osztás maradékát a véletlen számok intervallumának csökkentésére használjuk, amint azt fentebb említettük. A probléma itt az, hogy egy lineáris kongruens PRNG alsó bitjei kevésbé véletlenszerűek a magasabb bitekhez képest - az alsó n bitek periódusa legfeljebb 2 n . Ha az osztó kettő hatványa, akkor a maradék figyelembevétele a magasabb rendű bitek elvetését jelenti, ami a véletlenszerűség jelentős csökkenését eredményezi.
Végül meg kell jegyezni, hogy még finom generátor használata esetén is előfordulhat, hogy az algoritmus hibája a generátor helytelen használatából ered. Képzeljük el például, hogy az algoritmus Java implementációja a keverési folyamat minden egyes hívásához új generátort hoz létre anélkül, hogy paramétereket állítana be a konstruktorban. Az aktuális idő (System.currentTimeMillis()) lesz felhasználva a generátor inicializálására. Így két, egy ezredmásodpercnél kisebb időeltérésű hívás azonos permutációt ad. Ez szinte biztosan megtörténik, ha a keverés ismétlődően és gyorsan történik, ami a permutációk rendkívül egyenetlen eloszlását eredményezi. Ugyanez a probléma merülhet fel véletlen számok fogadásakor két különböző adatfolyamból. Helyesebb, ha a generátor egy statikus példányát használjuk, amely a keverési rutinon kívül van definiálva.