Tasowanie Fishera-Yatesa
Fishera -Yatesa to algorytm generowania losowej permutacji skończonej sekwencji - mówiąc wprost, algorytm tasuje sekwencję. Algorytm skutecznie umieszcza wszystkie elementy w kapeluszu; nieustannie określa następny element, losując element z kapelusza, aż nie pozostanie żaden element. Algorytm tworzy nieobciążoną permutację: każda permutacja jest równie prawdopodobna. Nowoczesna wersja algorytmu jest wydajna: zajmuje czas proporcjonalny do liczby tasowanych elementów i tasuje je na miejscu .
Tasowanie Fishera-Yatesa zostało nazwane na cześć Ronalda Fishera i Franka Yatesa , którzy jako pierwsi je opisali, i jest również znane jako tasowanie Knutha od imienia Donalda Knutha . Wariant tasowania Fishera-Yatesa, znany jako algorytm Sattolo , może być użyty do generowania losowych cyklicznych permutacji o długości n zamiast losowych permutacji.
Oryginalna metoda Fishera i Yatesa
Tasowanie Fishera-Yatesa w swojej pierwotnej formie zostało opisane w 1938 roku przez Ronalda Fishera i Franka Yatesa w ich książce Tabele statystyczne dla badań biologicznych, rolniczych i medycznych . W ich opisie algorytmu użyto ołówka i papieru; tablica liczb losowych zapewniła losowość. Podstawowa metoda generowania losowej permutacji liczb od 1 do N jest następująca:
- Zapisz liczby od 1 do N.
- Wybierz losową liczbę k z przedziału od jeden do liczby pozostałych niewylosowanych liczb (włącznie).
- Licząc od końca, wykreśl k -tą liczbę, która jeszcze nie została wykreślona, i zapisz ją na końcu oddzielnej listy.
- Powtarzaj od kroku 2, aż wszystkie cyfry zostaną wykreślone.
- Sekwencja liczb zapisanych w kroku 3 jest teraz losową permutacją oryginalnych liczb.
Pod warunkiem, że losowe liczby wybrane w kroku 2 powyżej są naprawdę losowe i nieobciążone, taka też będzie wynikowa permutacja. Fisher i Yates zadbali o to, aby opisać, jak uzyskać takie liczby losowe w dowolnym pożądanym zakresie z dostarczonych tabel w sposób, który pozwala uniknąć jakichkolwiek uprzedzeń. Zasugerowali również możliwość zastosowania prostszej metody — wybrania losowych liczb od jednego do N i odrzucenia wszelkich duplikatów — w celu wygenerowania pierwszej połowy permutacji i zastosowania bardziej złożonego algorytmu tylko do pozostałej połowy, gdzie wybranie zduplikowanej liczby byłoby w przeciwnym razie stają się frustrująco powszechne.
Nowoczesny algorytm
Nowoczesna wersja tasowania Fisher-Yates, przeznaczona do użytku komputerowego, została wprowadzona przez Richarda Durstenfelda w 1964 r. I spopularyzowana przez Donalda E. Knutha w The Art of Computer Programming jako „Algorytm P (tasowanie)”. Ani artykuł Durstenfelda, ani pierwsze wydanie The Art of Computer Programming autorstwa Knutha nie uznawały pracy Fishera i Yatesa; mogli o tym nie wiedzieć. Kolejne wydania książki Knutha The Art of Computer Programming wspominają o wkładzie Fishera i Yatesa.
Algorytm opisany przez Durstenfelda różni się od algorytmu podanego przez Fishera i Yatesa w niewielkim, ale znaczącym stopniu. Podczas gdy naiwna implementacja komputerowa metody Fishera i Yatesa niepotrzebnie traciłaby czas na liczenie pozostałych liczb w kroku 3 powyżej, rozwiązaniem Durstenfelda jest przeniesienie „trafionych” liczb na koniec listy poprzez zamianę ich z ostatnią niewybitą liczbą w każdym iteracja. złożoność czasową algorytmu do Displaystyle za naiwną realizację. Ta zmiana daje następujący algorytm (dla tablicy od zera ).
-- Przetasować tablicę a złożoną z n elementów (indeksy 0.. n -1): dla i od n −1 do 1 do j ← losowa liczba całkowita taka, że 0 ≤ j ≤ i zamieniamy a [ j ] i a [ i ]
Równoważna wersja, która tasuje tablicę w przeciwnym kierunku (od najniższego indeksu do najwyższego) to:
0
-- Przetasować tablicę a złożoną z n elementów (indeksy 0.. n -1): dla i od do n −2 do j ← losowa liczba całkowita taka, że i ≤ j < n zamień a [ i ] i a [ j ]
Przykłady
Metoda ołówka i papieru
Jako przykład przestawimy litery od A do H, używając oryginalnej metody Fishera i Yatesa . Zaczniemy od napisania liter na kartce papieru w ten sposób:
| Zakres | Rolka | Zadrapanie | Wynik |
|---|---|---|---|
| ABCDEFGH |
Teraz rzucamy losową liczbę k od 1 do 8 — niech to będzie 3 — i wykreślamy k -tą (tj. trzecią) literę na notatniku i zapisujemy wynik:
| Zakres | Rolka | Zadrapanie | Wynik |
|---|---|---|---|
| 1–8 | 3 | AB |
C |
Teraz wybieramy drugą losową liczbę, tym razem od 1 do 7: okazuje się, że to 4. Teraz wykreślamy czwartą literę, która nie została jeszcze wykreślona z notatnika — to jest litera E — i dodajemy ją do wyniku:
| Zakres | Rolka | Zadrapanie | Wynik |
|---|---|---|---|
| 1–7 | 4 | AB |
CE _ |
Teraz wybieramy kolejną losową liczbę od 1 do 6, a następnie od 1 do 5 i tak dalej, zawsze powtarzając proces wykreślania jak powyżej:
| Zakres | Rolka | Zadrapanie | Wynik |
|---|---|---|---|
| 1–6 | 5 | AB |
CE G |
| 1–5 | 3 | AB |
CEG D |
| 1–4 | 4 | AB |
CEGD H |
| 1–3 | 1 |
|
CEGDH A |
| 1–2 | 2 |
|
CEGDHA F |
|
|
CEGDHAF B |
Nowoczesna metoda
Teraz zrobimy to samo, używając wersji algorytmu Durstenfelda : tym razem, zamiast wykreślać wybrane litery i kopiować je gdzie indziej, zamienimy je ostatnią literą, która nie została jeszcze wybrana. Zaczniemy od wypisywania liter od A do H jak poprzednio:
| Zakres | Rolka | Zadrapanie | Wynik |
|---|---|---|---|
| ABCDEFGH |
W naszym pierwszym rzucie losujemy liczbę od 1 do 8: tym razem jest to 6, więc zamieniamy szóstą i ósmą literę na liście:
| Zakres | Rolka | Zadrapanie | Wynik |
|---|---|---|---|
| 1–8 | 6 | ABCDE H G | F |
Następną losową liczbę rzucamy od 1 do 7 i okazuje się, że to 2. W ten sposób zamieniamy drugą i siódmą literę i przechodzimy dalej:
| Zakres | Rolka | Zadrapanie | Wynik |
|---|---|---|---|
| 1–7 | 2 | A G CDEH | B.F _ |
Następna losowa liczba, którą wyrzucimy, to liczba od 1 do 6, a tak się składa, że jest to 6, co oznacza, że zostawiamy szóstą literę na liście (która po powyższej zamianie jest teraz literą H) na miejscu i po prostu przechodzimy do następnej krok. Ponownie postępujemy w ten sam sposób, aż do zakończenia permutacji:
| Zakres | Rolka | Zadrapanie | Wynik | ||||
|---|---|---|---|---|---|---|---|
| 1–6 | 6 | AGCDE | HBF _ | ||||
| 1–5 | 1 | E GCD | HBF _ | ||||
| 1–4 | 3 | EG D | C AHBF | ||||
| 1–3 | 3 | NP | D CAHBF | ||||
| 1–2 | 1 | G | E DCAHBF | ||||
W tym momencie nic więcej nie można zrobić, więc wynikowa permutacja to GEDCAHB F.
Warianty
Algorytm „na lewą stronę”.
Tasowanie Fishera-Yatesa, wdrożone przez Durstenfelda, jest tasowaniem na miejscu . Oznacza to, że mając wstępnie zainicjowaną tablicę, tasuje elementy tablicy na miejscu, zamiast tworzyć przetasowaną kopię tablicy. Może to być zaletą, jeśli tablica do przetasowania jest duża.
Aby jednocześnie zainicjować i przetasować tablicę, można uzyskać nieco większą wydajność, wykonując wersję przetasowania „od wewnątrz”. W tej wersji kolejno umieszcza się element o numerze i na losowej pozycji wśród pierwszych i pozycji w tablicy, po przesunięciu elementu poprzednio zajmującego tę pozycję na pozycję i . W przypadku, gdy przypadkową pozycją jest liczba i , to „przeniesienie” (w to samo miejsce) obejmuje niezainicjowaną wartość, ale to nie ma znaczenia, ponieważ wartość jest wtedy natychmiast nadpisywana. Nie jest wymagana oddzielna inicjalizacja i nie jest przeprowadzana żadna wymiana. W typowym przypadku, gdy źródło jest zdefiniowane przez jakąś prostą funkcję, taką jak liczby całkowite od 0 do n - 1, źródło można po prostu zastąpić funkcją, ponieważ źródło nigdy nie jest zmieniane podczas wykonywania.
0
Aby zainicjować tablicę a składającą się z n elementów do losowo przetasowanej kopii source , obie oparte na 0: for i from to n − 1 do j ← losowa liczba całkowita taka, że 0 ≤ j ≤ i if j ≠ i a [ i ] ← a [ j ] za [ j ] ← źródło [ ja ]
Tasowanie na lewą stronę można uznać za poprawne przez indukcję . Zakładając doskonały generator liczb losowych, każdy z n ! różne sekwencje liczb losowych, które można uzyskać z wywołań losowych , dadzą inną permutację wartości, więc wszystkie z nich są uzyskiwane dokładnie raz. Warunek sprawdzający, czy j ≠ i można pominąć w językach, które nie mają problemów z dostępem do niezainicjowanych wartości tablicowych. Eliminuje to n gałęzi warunkowych kosztem nadmiarowych przypisań H n ≈ ln n + γ .
Kolejną zaletą tej techniki jest to, że n , liczba elementów w źródle , nie musi być znana z góry; musimy tylko być w stanie wykryć koniec danych źródłowych, gdy zostanie osiągnięty. Poniżej tablicy a jest budowane iteracyjnie zaczynając od pustej tablicy, a .długość reprezentuje aktualną liczbę widocznych elementów.
Aby zainicjować pustą tablicę a losowo przetasowaną kopią źródła , którego długość nie jest znana: while source .moreDataAvailable j ← losowa liczba całkowita taka, że 0 ≤ j ≤ a .length if j = a .length a .append( source .next) else a .append( a [ j ]) a [ j ] ← źródło .następny
Algorytm Sattolo
|
Permutacja cykliczna _ |
Przykład |
|---|---|
| BCDA | ABCD→DABC→CDAB→ BCDA →ABCD... |
| DABC | ABCD→BCDA→CDAB→ DABC →ABCD... |
| BDAC | ABCD→CADB→DCBA→ BDAC →ABCD... |
| CADB | ABCD→BDAC→DCBA→ CADB →ABCD... |
| CDBA | ABCD→DCAB→BADC→ CDBA →ABCD... |
| DCAB | ABCD→CDBA→BADC→ DCAB →ABCD... |
|
Sześć (3!) cyklicznych permutacji ABCD wygenerowanych przez algorytm Sattolo |
|
Bardzo podobny algorytm został opublikowany w 1986 roku przez Sandrę Sattolo do generowania równomiernie rozłożonych cykli o (maksymalnej) długości n . Jedyna różnica między algorytmami Durstenfelda i Sattolo polega na tym, że w tym drugim, w kroku 2 powyżej, liczba losowa j jest wybierana z zakresu od 1 do i -1 (a nie od 1 do i ) włącznie. Ta prosta zmiana modyfikuje algorytm w taki sposób, że wynikowa permutacja zawsze składa się z jednego cyklu.
W rzeczywistości, jak opisano poniżej, dość łatwo jest przypadkowo zaimplementować algorytm Sattolo, gdy zamierzone jest zwykłe tasowanie Fishera-Yatesa. Spowoduje to zniekształcenie wyników, powodując wybranie permutacji z mniejszego zestawu ( n −1)! cykli o długości N , zamiast z pełnego zestawu wszystkich n ! możliwe permutacje.
Fakt, że algorytm Sattolo zawsze wytwarza cykl o długości n , można wykazać przez indukcję . Załóżmy przez indukcję, że po początkowej iteracji pętli pozostałe iteracje permutują pierwsze n - 1 elementów zgodnie z cyklem o długości n - 1 (te pozostałe iteracje to po prostu algorytm Sattolo zastosowany do tych pierwszych n - 1 elementów). Oznacza to, że śledzenie elementu początkowego do jego nowej pozycji p , następnie elementu pierwotnie w pozycji p do nowej pozycji itd. Powrót do pozycji początkowej następuje dopiero po odwiedzeniu wszystkich innych pozycji. Załóżmy, że początkowa iteracja zamieniła ostatni element z tym, który znajduje się na (niekońcowej) pozycji k , i że późniejsza permutacja pierwszych n - 1 elementów przesunęła go następnie na pozycję l ; porównujemy permutację π wszystkich n elementów z pozostałą permutacją σ pierwszych n - 1 elementów. Śledząc kolejne pozycje, jak już wspomniano, nie ma różnicy między π i σ , aż do osiągnięcia pozycji k . Ale wtedy, pod π element pierwotnie w pozycji k jest przesuwany do pozycji końcowej, a nie do pozycji l , a element pierwotnie w pozycji końcowej jest przesuwany do pozycji l . Od tego momentu sekwencja pozycji dla π ponownie jest zgodna z sekwencją dla σ , a wszystkie pozycje zostaną odwiedzone przed powrotem do pozycji początkowej, zgodnie z wymaganiami.
Jeśli chodzi o równe prawdopodobieństwo permutacji, wystarczy zauważyć, że zmodyfikowany algorytm obejmuje ( n −1)! różne możliwe sekwencje utworzonych liczb losowych, z których każda wyraźnie tworzy inną permutację i każda z nich występuje - zakładając, że źródło liczb losowych jest bezstronne - z równym prawdopodobieństwem. ( n −1)! tak wytworzone różne permutacje dokładnie wyczerpują zbiór cykli o długości n : każdy taki cykl ma unikalny zapis cyklu z wartością n na pozycji końcowej, co pozwala na ( n −1)! permutacje pozostałych wartości, aby wypełnić inne pozycje zapisu cyklu.
Przykładowa implementacja algorytmu Sattolo w Pythonie to:
z losowego importu randrange def sattolo_cycle ( pozycji ) -> Brak : """Algorytm Sattolo.""" i = len ( pozycje ) while i > 1 : i = i - 1 j = randrange ( i ) # 0 <= j < = i-1 pozycje [ j ], pozycje [ i ] = pozycje [ i ], pozycje [ j ]
Porównanie z innymi algorytmami tasowania
Asymptotyczna złożoność czasowa i przestrzenna tasowania Fishera-Yatesa jest optymalna. W połączeniu z wysokiej jakości bezstronnym źródłem liczb losowych gwarantuje to również uzyskanie obiektywnych wyników. W porównaniu z niektórymi innymi rozwiązaniami ma również tę zaletę, że jeśli potrzebna jest tylko część wynikowej permutacji, można ją zatrzymać w połowie lub nawet wielokrotnie zatrzymać i ponownie uruchomić, generując permutację przyrostowo w razie potrzeby.
Naiwna metoda
Naiwna metoda zamiany każdego elementu na inny element wybrany losowo spośród wszystkich elementów jest stronnicza i zasadniczo zepsuta. Różne miały różne prawdopodobieństwo wygenerowania dla każdego , liczba różnych permutacji , nie dzieli równomiernie liczby losowych wyników algorytmu, . W szczególności, zgodnie z postulatem Bertranda, będzie co najmniej jedna liczba pierwsza między i , a ta liczba podzieli , ale nie dziel .
from random import randrange def naive_shuffle ( items ) -> None : """Metoda naiwna. To jest przykład tego, czego nie należy robić - zamiast tego użyj Fishera-Yatesa.""" n = len ( itemów ) dla i w zakresie ( n ): j = przedział losowy ( n ) # 0 <= j <= n-1 pozycji [ j ], pozycji [ i ] = pozycji [ i ], pozycji [ j ]
Sortowanie
Alternatywna metoda przypisuje losową liczbę każdemu elementowi zestawu do przetasowania, a następnie sortuje zestaw zgodnie z przypisanymi liczbami. Metoda sortowania ma taką samą asymptotyczną złożoność czasową jak Fisher-Yates: chociaż ogólne sortowanie to O ( n log n ), liczby są efektywnie sortowane przy użyciu sortowania Radix w czasie O ( n ). Podobnie jak tasowanie Fishera-Yatesa, metoda sortowania daje obiektywne wyniki. Należy jednak uważać, aby przypisane liczby losowe nigdy się nie duplikowały, ponieważ algorytmy sortowania zazwyczaj nie porządkują elementów losowo w przypadku remisu. Ponadto ta metoda wymaga asymptotycznie większej przestrzeni: O ( n ) dodatkowej przestrzeni do przechowywania liczb losowych w porównaniu z O (1) przestrzenią dla tasowania Fishera – Yatesa. Na koniec zauważamy, że metoda sortowania ma prostą równoległą , w przeciwieństwie do losowania Fishera-Yatesa, które jest sekwencyjne.
Wariantem powyższej metody, który był używany w językach obsługujących sortowanie za pomocą funkcji porównania określonych przez użytkownika, jest tasowanie listy przez sortowanie jej za pomocą funkcji porównania, która zwraca losowe wartości. Jest to jednak wyjątkowo zła metoda : bardzo prawdopodobne jest, że wygeneruje wysoce niejednorodne rozkłady, które dodatkowo w dużym stopniu zależą od zastosowanego algorytmu sortowania. Załóżmy na przykład, że sortowania używany jest algorytm sortowania, w którym jako pierwszy element przestawny wybrano stały element . Algorytm zaczyna porównywać element obrotowy ze wszystkimi innymi elementami, aby podzielić je na mniejsze i większe od niego, a względne rozmiary tych grup określą ostateczne miejsce elementu obrotowego. permutacji losowej o równomiernym rozkładzie każda możliwa pozycja końcowa powinna być równie prawdopodobna dla elementu obrotu, ale jeśli każde z początkowych porównań zwróci „mniej” lub „większy” z równym prawdopodobieństwem, to ta pozycja będzie miała rozkład dwumianowy dla p = 1/2, co daje pozycje w pobliżu środka sekwencji z dużo większym prawdopodobieństwem niż pozycje w pobliżu końców. Randomizowane funkcje porównawcze zastosowane do innych metod sortowania, takich jak sortowanie przez scalanie , mogą dawać wyniki, które wydają się bardziej jednolite, ale też takie nie są, ponieważ łączenie dwóch sekwencji poprzez wielokrotne wybieranie jednej z nich z równym prawdopodobieństwem (dopóki wybór nie zostanie wymuszony przez wyczerpanie jednego sekwencja) nie daje wyników o równomiernym rozkładzie; zamiast tego prawdopodobieństwo wyboru sekwencji powinno być proporcjonalne do liczby pozostałych w niej elementów [ potrzebne źródło ] . W rzeczywistości żadna metoda, która wykorzystuje tylko dwukierunkowe zdarzenia losowe z równym prawdopodobieństwem ( „rzut monetą” ), powtarzane ograniczoną liczbę razy, nie może wytworzyć permutacji sekwencji (więcej niż dwóch elementów) o jednolitym rozkładzie, ponieważ każde wykonanie ścieżka będzie miała jako prawdopodobieństwo liczbę wymierną o mianowniku potęgi 2 , natomiast wymagane prawdopodobieństwo 1/ n ! dla każdej możliwej permutacji nie ma tej formy [ potrzebne źródło ] .
Zasadniczo ta metoda tasowania może nawet skutkować awariami programu, takimi jak nieskończone pętle lub naruszenia dostępu, ponieważ poprawność algorytmu sortowania może zależeć od właściwości relacji porządku (takich jak przechodniość ), których z pewnością nie będzie miało porównanie dające losowe wartości. Chociaż tego rodzaju zachowanie nie powinno wystąpić w przypadku procedur sortowania, które nigdy nie wykonują porównania, którego wynik można z całą pewnością przewidzieć (na podstawie poprzednich porównań), mogą istnieć uzasadnione powody celowego dokonywania takich porównań. Na przykład fakt, że każdy element powinien być równy samemu sobie, pozwala na użycie ich jako wartości wskaźnikowej ze względu na wydajność, aw takim przypadku funkcja porównania losowego zepsułaby algorytm sortowania.
Potencjalne źródła uprzedzeń
Podczas wdrażania tasowania Fishera-Yatesa należy zachować ostrożność, zarówno podczas implementacji samego algorytmu, jak i generowania liczb losowych, na których jest on zbudowany, w przeciwnym razie wyniki mogą wykazywać wykrywalne obciążenie. Poniżej wymieniono kilka typowych źródeł uprzedzeń.
Błędy implementacyjne
Częstym błędem podczas wdrażania tasowania Fishera – Yatesa jest wybieranie losowych liczb z niewłaściwego zakresu. Może się wydawać, że wadliwy algorytm działa poprawnie, ale nie generuje każdej możliwej permutacji z równym prawdopodobieństwem, a niektórych permutacji może wcale nie generować. Na przykład typowym błędem różnicowym byłoby wybranie indeksu j wpisu do zamiany w powyższym przykładzie tak, aby był zawsze ściśle mniejszy niż indeks i wpisu, z którym zostanie on zamieniony. To zmienia tasowanie Fishera-Yatesa w algorytm Sattolo , który tworzy tylko permutacje składające się z jednego cyklu obejmującego wszystkie elementy: w szczególności przy tej modyfikacji żaden element tablicy nie może nigdy znaleźć się w swojej pierwotnej pozycji.
Podobnie, zawsze wybieranie j z całego zakresu prawidłowych indeksów tablicy w każdej iteracji również daje wynik, który jest obciążony, choć mniej oczywisty. Można to zobaczyć na podstawie faktu, że w ten sposób otrzymujemy n n różnych możliwych sekwencji zamian, podczas gdy jest ich tylko n ! możliwe permutacje n -elementowej tablicy. Ponieważ n n nigdy nie może być równo podzielne przez n ! gdy n > 2 (ponieważ ta ostatnia jest podzielna przez n −1, co nie ma wspólnych czynników pierwszych z n ), niektóre permutacje muszą być tworzone przez więcej n n sekwencji zamian niż inne. Jako konkretny przykład tego błędu, obserwuj rozkład możliwych wyników tasowania trzyelementowej tablicy [1, 2, 3]. Istnieje 6 możliwych permutacji tej tablicy (3! = 6), ale algorytm daje 27 możliwych przetasowań (3 3 = 27). W tym przypadku [1, 2, 3], [3, 1, 2] i [3, 2, 1] wynikają z 4 z 27 przetasowań, podczas gdy każda z pozostałych 3 permutacji występuje w 5 z 27 tasuje.
Macierz po prawej pokazuje prawdopodobieństwo, że każdy element na liście o długości 7 znajdzie się na dowolnej innej pozycji. Zauważ, że dla większości elementów znalezienie się w pierwotnej pozycji (główna przekątna macierzy) ma najniższe prawdopodobieństwo, a przesunięcie o jedno miejsce wstecz ma największe prawdopodobieństwo.
Odchylenie modulo
Tasowanie Fishera-Yatesa polega na wybraniu równomiernie rozłożonych losowych liczb całkowitych z różnych zakresów. Jednak większość generatorów liczb losowych — zarówno prawdziwych, jak i pseudolosowych — zapewnia bezpośrednio tylko liczby w ustalonym zakresie od 0 do RAND_MAX, aw niektórych bibliotekach RAND_MAX może wynosić nawet 32767. Prosty i często używany sposób wymuszania takich liczb pożądanym zakresem jest zastosowanie operatora modulo ; to znaczy podzielić je przez rozmiar zakresu i wziąć resztę. Jednak potrzeba generowania liczb losowych w tasowaniu Fishera-Yatesa w każdym zakresie od 0–1 do 0– n prawie gwarantuje, że niektóre z tych zakresów nie podzielą równomiernie naturalnego zakresu generatora liczb losowych. Zatem reszty nie zawsze będą równomiernie rozłożone, a co gorsza, odchylenie będzie systematycznie faworyzować małe reszty.
Załóżmy na przykład, że twoje źródło liczb losowych podaje liczby od 0 do 99 (tak jak w przypadku oryginalnych tabel Fishera i Yatesa) i że chcesz otrzymać nieobciążoną liczbę losową od 0 do 15. Jeśli po prostu podzielisz liczby do 16 i weź resztę, przekonasz się, że liczby 0–3 występują o około 17% częściej niż inne. Dzieje się tak, ponieważ 16 nie dzieli równo 100: największa wielokrotność 16 mniejsza lub równa 100 to 6 × 16 = 96, a to liczby z niepełnego zakresu 96–99 powodują błąd. Najprostszym sposobem rozwiązania problemu jest odrzucenie tych liczb przed przyjęciem reszty i kontynuowanie prób, aż pojawi się liczba z odpowiedniego zakresu. Chociaż w zasadzie mogłoby to w najgorszym przypadku trwać wiecznie, oczekiwana liczba ponownych prób zawsze będzie mniejsza niż jedna.
Podobny problem występuje w implementacjach, które najpierw generują losową liczbę zmiennoprzecinkową — zwykle z zakresu [0,1] — a następnie mnożą ją przez rozmiar żądanego zakresu i zaokrąglają w dół. Problem polega na tym, że losowe liczby zmiennoprzecinkowe, jakkolwiek starannie generowane, zawsze mają tylko skończoną precyzję. Oznacza to, że istnieje tylko skończona liczba możliwych wartości zmiennoprzecinkowych w danym zakresie, a jeśli zakres zostanie podzielony na kilka segmentów, które nie dzielą tej liczby równomiernie, niektóre segmenty zakończą się większą liczbą możliwych wartości niż inne . Chociaż wynikające z tego nastawienie nie będzie wykazywać tego samego systematycznego trendu spadkowego, co w poprzednim przypadku, nadal będzie występować.
Generatory pseudolosowe
| kawałki nasion | maksymalna długość listy |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 3 | 3 |
| 5 | 4 |
| 7 | 5 |
| 10 | 6 |
| 13 | 7 |
| 16 | 8 |
| 22 | 10 |
| 24 | 10 |
| 32 | 12 |
| 48 | 16 |
| 64 | 20 |
| 128 | 34 |
| 160 | 40 |
| 226 | 52 |
| 256 | 57 |
| 512 | 98 |
| 1024 | 170 |
| 1600 | 245 |
| 19937 | 2080 |
| 44497 | 4199 |
Dodatkowy problem pojawia się, gdy tasowanie Fishera-Yatesa jest używane z generatorem liczb pseudolosowych lub PRNG: ponieważ sekwencja liczb wyprowadzanych przez taki generator jest całkowicie określona przez jego stan wewnętrzny na początku sekwencji, tasowanie napędzane przez takie generator nie może prawdopodobnie wytworzyć bardziej wyraźnych permutacji, niż generator ma różne możliwe stany. Nawet jeśli liczba możliwych stanów przekracza liczbę permutacji, nieregularny charakter odwzorowania sekwencji liczb na permutacje oznacza, że niektóre permutacje będą występować częściej niż inne. Zatem, aby zminimalizować błąd systematyczny, liczba stanów PRNG powinna przekraczać liczbę permutacji o co najmniej kilka rzędów wielkości.
Na przykład wbudowany generator liczb pseudolosowych dostarczany przez wiele języków programowania i/lub bibliotek może często mieć tylko 32 bity stanu wewnętrznego, co oznacza, że może wygenerować tylko 2 32 różne sekwencje liczb. Jeśli taki generator zostanie użyty do przetasowania talii 52 kart do gry , może wyprodukować tylko bardzo mały ułamek z 52! ≈ 2 225,6 możliwych permutacji. Generator z mniej niż 226 bitami stanu wewnętrznego nie jest w stanie wytworzyć wszystkich możliwych permutacji talii 52 kart.
Żaden generator liczb pseudolosowych nie może wygenerować bardziej odrębnych sekwencji, zaczynając od punktu inicjalizacji, niż istnieją różne wartości początkowe, z którymi można go zainicjować. Zatem generator, który ma 1024 bity stanu wewnętrznego, ale który jest inicjowany 32-bitowym ziarnem, może nadal generować tylko 2 32 różne permutacje zaraz po inicjalizacji. Może wytworzyć więcej permutacji, jeśli użyje się generatora wiele razy, zanim zacznie się go używać do generowania permutacji, ale jest to bardzo nieefektywny sposób zwiększania losowości: przypuśćmy, że można zorganizować użycie generatora losowej liczby do miliarda , powiedzmy 2 30 dla uproszczenia, czasy między inicjalizacją a wygenerowaniem permutacji, to liczba możliwych permutacji nadal wynosi tylko 2 62 .
Kolejny problem pojawia się, gdy prosty liniowy kongruencja PRNG jest używany z opisaną powyżej metodą redukcji zakresu typu „dziel i weź resztę”. Problem polega na tym, że bity niskiego rzędu liniowego kongruencji PRNG z modulo 2 e są mniej losowe niż bity wyższego rzędu: n bitów samego generatora ma okres co najwyżej 2 n . Gdy dzielnik jest potęgą dwójki, wzięcie reszty zasadniczo oznacza odrzucenie bitów wyższego rzędu, tak że jeden z nich ma znacznie mniej losową wartość. LCG ma pierwsze modulo, obowiązują inne zasady , ale takie generatory są rzadkie. To jest przykład ogólnej zasady, że złej jakości RNG lub PRNG będzie generować tasowanie niskiej jakości.
Zobacz też
- RC4 , szyfr strumieniowy oparty na tasowaniu tablicy
- Pobieranie próbek ze zbiornika , w szczególności algorytm R, który jest specjalizacją tasowania Fishera – Yatesa