Dlaczego ten algorytm tasowania jest nieprawidłowy?

Question

Przed Czytałem o Fisher-Yates, jest to algorytm wymyśliłem:

def sort(arr): 
    for i in range(len(arr)): 
     swap(arr, i, rand.randint(0, len(arr) - 1)) 

Z mojego zrozumienia, jedyną różnicą między tym i Fisher-Yates jest to, że zamiast:

swap(arr, i, rand.randint(0, len(arr) - 1)) 

powinienem napisać:

swap(arr, i, rand.randint(i, len(arr) - 1)) 

mógłby ktoś wyjaśnić jak pierwszy algorytm jest błędna? (tj. nie powoduje losowego przetasowania).

Answer 1

Z Wikipedii:

Podobnie, zawsze wybierając j od całego szeregu ważnych indeksów tablicy na każdej iteracji produkuje także wynik, który jest stronniczy, aczkolwiek mniej oczywiście tak. Można to zauważyć na podstawie faktu, że czyniąc to daje różne sekwencje zamiany, podczas gdy są tylko n! możliwe permutacje tablicy n-elementowej. Ponieważ n ⁿ nigdy nie będzie równomiernie podzielne przez n! gdy n> 2 (jako że ta ostatnia jest podzielna przez n-1, która nie współdzieli czynników pierwotnych z n), niektóre permutacje muszą być wytworzone przez większą liczbę sekwencji zamiany niż inne. Jako konkretny przykład tego błędu, obserwuj rozkład możliwych wyników tasowania trzyelementowego układu [1, 2, 3]. Istnieje 6 możliwych permutacji tej tablicy (3! = 6), ale algorytm tworzy 27 możliwych tasowań (33 = 27). W tym przypadku, [1, 2, 3], [3, 1, 2] i [3, 2, 1] są wynikiem 4 z 27 tasowań, podczas gdy każda z pozostałych 3 permutacji występuje w 5 z 27 tasuje.

Zasadniczo wprowadzasz do shuffle subtelne odchylenie, które powoduje, że niektóre permutacje pojawiają się nieco częściej niż inne. Często nie jest to bardzo zauważalne, ale może sprawić, że niektóre wrażliwe aplikacje (na przykład symulacje Monte Carlo na permutacjach) nie dadzą dokładnych odpowiedzi.