¿Por qué este algoritmo de mezcla es incorrecto?

Question

Antes de leer acerca de Fisher-Yates, este es el algoritmo que se me ocurrió:

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

Desde mi entender, la única diferencia entre este y Fisher-Yates es que en lugar de:

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

que debería escribir:

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

Podría alguien explicar cómo el primer algoritmo es incorrecta? (es decir, no produce un aleatorio aleatorio).

Answer 1

De Wikipedia:

mismo modo, seleccionando siempre j de toda la gama de índices de matriz válidos en cada iteración también produce un resultado que es parcial, aunque menos obvio. Esto se puede ver en el hecho de que al hacerlo arroja n ⁿ distintas secuencias posibles de swaps, mientras que solo hay n! posibles permutaciones de una matriz de n elementos. Dado que n ⁿ nunca puede ser divisible uniformemente por n! cuando n> 2 (como este último es divisible por n-1, que no comparte factores primos con n), algunas permutaciones deben producirse por más de las n ⁿ secuencias de swaps que otras. Como un ejemplo concreto de este sesgo, observe la distribución de los posibles resultados de mezclar una matriz de tres elementos [1, 2, 3]. Hay 6 posibles permutaciones de esta matriz (3! = 6), pero el algoritmo produce 27 combinaciones posibles (33 = 27). En este caso, [1, 2, 3], [3, 1, 2] y [3, 2, 1] resultan de 4 de las 27 mezclas, mientras que cada una de las 3 permutaciones restantes ocurre en 5 de las 27 baraja

Básicamente, está introduciendo un sesgo sutil en la reproducción aleatoria, lo que hará que algunas permutaciones surjan con más frecuencia que otras. A menudo no es muy notable, pero podría hacer que algunas aplicaciones delicadas (por ejemplo, simulaciones de Monte Carlo en permutaciones) no produzcan respuestas precisas.