Mezcla Fisher-Yates

El algoritmo de Fisher-Yates es un algoritmo para mezclar una secuencia finita. El algoritmo toma una lista de todos los elementos de la secuencia y determina continuamente el siguiente elemento de la secuencia mezclada extrayendo aleatoriamente un elemento de la lista hasta que no quede ningún elemento. El algoritmo produce una permutación imparcial: cada permutación es igualmente probable. La versión moderna del algoritmo toma un tiempo proporcional a la cantidad de elementos que se mezclan y los mezcla en su lugar.

El algoritmo Fisher-Yates recibe su nombre de Ronald Fisher y Frank Yates, quienes lo describieron por primera vez. También se lo conoce como el algoritmo Knuth, en honor a Donald Knuth. Una variante del algoritmo Fisher-Yates, conocido como el algoritmo Sattolo, se puede utilizar para generar permutaciones cíclicas aleatorias de longitud n en lugar de permutaciones aleatorias.

El algoritmo Fisher-Yates, en su forma original, fue descrito en 1938 por Ronald Fisher y Frank Yates en su libro Tablas estadísticas para la investigación biológica, agrícola y médica. En su descripción del algoritmo se utilizó lápiz y papel; una tabla de números aleatorios proporcionó la aleatoriedad. El método básico dado para generar una permutación aleatoria de los números del 1 al N es el siguiente:

1. Escriba los números de 1 a 1 N.
2. Elija un número aleatorio k entre uno y el número de números inconclusivos restantes (inclusive).
3. Contando desde el extremo bajo, golpea el kt número aún no se ha dado cuenta, y escríbalo al final de una lista separada.
4. Repetir desde el paso 2 hasta que todos los números hayan sido eliminados.
5. La secuencia de números escritos en el paso 3 es ahora una permutación aleatoria de los números originales.

Siempre que los números aleatorios escogidos en el paso 2 sean verdaderamente aleatorios e imparciales, también lo será la permutación resultante. Fisher y Yates se ocuparon de describir cómo obtener dichos números aleatorios en cualquier rango deseado a partir de las tablas proporcionadas de una manera que evite cualquier sesgo. También sugirieron la posibilidad de utilizar un método más simple (seleccionar números aleatorios de 1 a N y descartar los duplicados) para generar la primera mitad de la permutación, y aplicar el algoritmo más complejo solo a la mitad restante, donde, de lo contrario, elegir un número duplicado se volvería frustrantemente común.

La versión moderna del algoritmo Fisher-Yates, diseñado para uso informático, fue presentado por Richard Durstenfeld en 1964 y popularizado por Donald E. Knuth en El arte de la programación informática como "Algoritmo P (Mezcla aleatoria)". Ni el artículo de Durstenfeld ni la primera edición de Knuth de El arte de la programación informática reconocieron el trabajo de Fisher y Yates; es posible que no estuvieran al tanto de él. Las ediciones posteriores de El arte de la programación informática de Knuth mencionan la contribución de Fisher y Yates.

El algoritmo descrito por Durstenfeld es más eficiente que el dado por Fisher y Yates: mientras que una ingenua implementación de la computadora del método Fisher y Yates pasaría tiempo sin necesidad contando los números restantes en el paso 3 arriba, la solución de Durstenfeld es mover los números de "struck" al final de la lista al cambiarlos con el último número de desconfianza en cada iteración. Esto reduce la complejidad del tiempo del algoritmo ${\displaystyle O(n)}$ en comparación con ${\displaystyle O(n^{2}}$ para la ingenua implementación. Este cambio da el siguiente algoritmo (para un array basado en cero).

-- Para eliminar un array a de n elementos (indices 0.n-1):
para i desde n−1 abajo 1 do j ← entero al azar tal que 0 ≤ j ≤ icambio a[j] y a[i]

Una versión equivalente que baraja la matriz en la dirección opuesta (del índice más bajo al más alto) es:

-- Para eliminar un array a de n elementos (indices 0.n-1):
para i desde 0 a n−2 do j ← entero entero tal que i ≤ j ≤ n-1cambio a[i] y a[j]

Este ejemplo permuta las letras de la A a la H utilizando el método original de Fisher y Yates, comenzando con las letras en orden alfabético:

Se selecciona un número aleatorio j entre 1 y 8. Si, por ejemplo, j=3, se tacha la tercera letra del bloc de notas y se escribe como resultado:

Se elige un segundo número aleatorio, esta vez entre 1 y 7. Si el número es 4, se elimina la cuarta letra que aún no se ha eliminado del bloc de notas y se añade al resultado:

El siguiente número aleatorio se selecciona del 1 al 6, y luego del 1 al 5, y así sucesivamente, repitiendo siempre el proceso de eliminación como se indicó anteriormente:

En la versión del algoritmo de Durstenfeld, en lugar de eliminar las letras elegidas y copiarlas en otro lugar, se las intercambia por la última letra que aún no se ha elegido. Se empieza con las letras de la A a la H como antes:

Seleccione un número aleatorio j del 1 al 8 y luego intercambie las letras j y 8.ª. Por ejemplo, si el número aleatorio es 6, intercambie las letras 6.ª y 8.ª de la lista:

Se selecciona el siguiente número aleatorio entre 1 y 7 y la letra seleccionada se intercambia con la séptima letra. Si es 2, por ejemplo, se intercambian la segunda y la séptima letra:

El proceso se repite hasta que se completa la permutación:

Después de ocho pasos, el algoritmo está completo y la permutación resultante es G E D C A H B F.

Este ejemplo muestra una implementación sencilla en Python de la combinación Fisher-Yates.

importación al azar def shuffle()n: int) - No. lista[int]: números = lista()rango()n) shuffled = [] mientras números: k = al azar.Randy.()0, Len()números) - 1) shuffled.apéndice()números[k]) números.pop()k) Regreso shuffled

Este ejemplo muestra una implementación simple en JavaScript de la combinación Fisher-Yates.

función shuffle Array()array) {} para ()Deja i = array.longitud - 1; i >= 1; i--) {} const j = Matemáticas.planta baja()Matemáticas.al azar() * ()i + 1)); [array[i] array[j]] = [array[j] array[i]] }}

La mezcla de Fisher-Yates, tal como la implementó Durstenfeld, es una mezcla en el lugar. Es decir, dada una matriz preinicializada, mezcla los elementos de la matriz en el lugar, en lugar de producir una copia mezclada de la matriz. Esto puede ser una ventaja si la matriz que se va a mezclar es grande.

Para inicializar y mezclar simultáneamente una matriz, se puede lograr un poco más de eficiencia haciendo una versión "de adentro hacia afuera" de la mezcla. En esta versión, uno coloca sucesivamente el elemento número i en una posición aleatoria entre las primeras i posiciones en la matriz, después de mover el elemento que ocupaba previamente esa posición a la posición i. No se necesita una inicialización separada. Debido a que source nunca se altera durante la ejecución, hay una flexibilidad considerable en cómo se obtienen los valores. En el caso común donde source se define por alguna función simple, como los números enteros de 0 a n − 1, source puede simplemente reemplazarse con la función.

Para inicializar un array a[] of n elementos a una copia aleatoriamente encogida fuente[], ambos basados en 0:
 para i desde 0 a n − 1 do j ← entero al azar tal que 0 ≤ j ≤ i a[i← fuente[i]
 a[i← a[j]
 a[j← fuente[i]

La asignación inicial aparentemente redundante a a[i] está ahí para asegurar que el siguiente acceso a a[j] no sea una variable no inicializada en el caso de que i = j. El valor de inicialización no importa; cero serviría igual de bien. En ese caso, el valor copiado en la segunda asignación a a[i] tampoco importa, ya que se sobrescribe inmediatamente con la asignación a a[j], pero muchos lenguajes populares (incluidos específicamente C y C++, con excepciones limitadas que no se aplican aquí) establecen que simplemente leer un valor no inicializado es un comportamiento indefinido y, por lo tanto, un error de programación. Si este acceso es, en la práctica, inofensivo (como ocurre en casi todos los ordenadores comunes), se puede omitir la asignación inicial.

Alternativamente, podrías probar si i = j y omitir cualquier asignación a a[i] si son iguales, pero el ahorro de n asignaciones redundantes se produce a costa de n bifurcaciones condicionales, Hn ≈ ln n + γ de las cuales serán impredecibles. Para un n moderado, esto puede resultar más costoso que las asignaciones.

Se puede comprobar que la mezcla de dentro a fuera es correcta por inducción. Después de la iteración del bucle i, los primeros i elementos de la matriz contienen una permutación aleatoria. Cada iteración del bucle mantiene esta propiedad mientras aumenta i. Alternativamente, se puede demostrar que hay n! secuencias diferentes de números aleatorios j, y cada una corresponde a una permutación diferente. Por lo tanto, cada permutación se obtiene exactamente una vez. Suponiendo un generador de números aleatorios perfecto, todas ocurrirán con la misma probabilidad.

Otra ventaja de esta variante es que no es necesario conocer de antemano n, el número de elementos de la fuente; solo es necesario poder detectar el final de los datos de la fuente cuando se alcanza. A continuación, la matriz a se construye de forma iterativa a partir de un valor vacío, y a.length representa el número actual de elementos vistos:

Para inicializar un array vacío a a una copia aleatoriamente encogida fuente cuya longitud no se conoce:
 mientras fuente.másDataDisponible
 j ← entero al azar tal que 0 ≤ j ≤ a. longitud
 si j) a. longitud
 a.append(fuente.next)
 más a.append(a[j])
 a[j← fuente.next

Es interesante comparar el orden aleatorio regular y el orden aleatorio inverso cuando se eligen k ≤ n de n elementos. El algoritmo regular requiere una matriz de n entradas inicializada con los valores de entrada, pero luego requiere solo k iteraciones para elegir una muestra aleatoria de k elementos. Por lo tanto, toma O(k) tiempo y n espacio.

El algoritmo de adentro hacia afuera se puede implementar utilizando únicamente una matriz de k elementos a. Los elementos a[i] para i ≥ k simplemente no se almacenan. Durante la iteración i ≥ k, si j < k, source[i] se almacena allí y se descarta el valor anterior. Si j ≥ k, entonces source[i] se descarta.

Si se supone que la fuente se puede generar de manera procedimental y, por lo tanto, no ocupa espacio, es necesario realizar todas las n iteraciones para finalizar la salida, pero solo k elementos de almacenamiento. En comparación con el algoritmo regular, los requisitos de espacio y tiempo se invierten.

Otra diferencia es que el algoritmo regular necesita saber n de antemano, pero no k; no es necesario decidir de antemano cuánta salida es suficiente. El algoritmo inverso necesita saber (un límite superior de) k de antemano, pero no n; no es necesario decidir de antemano cuánta entrada es suficiente.

En 1986 Sandra Sattolo publicó un algoritmo muy similar para generar ciclos distribuidos uniformemente de longitud (máxima) n. La única diferencia entre los algoritmos de Durstenfeld y Sattolo es que en este último, en el paso 2 mencionado anteriormente, el número aleatorio j se elige del rango entre 1 y i−1 (en lugar de entre 1 y i) inclusive. Este simple cambio modifica el algoritmo de modo que la permutación resultante siempre consiste en un solo ciclo.

De hecho, como se describe a continuación, es bastante fácil implementar accidentalmente el algoritmo de Sattolo cuando se pretende realizar la mezcla Fisher-Yates habitual. Esto sesgará los resultados al hacer que las permutaciones se seleccionen del conjunto más pequeño de (n−1)! ciclos de longitud N, en lugar de del conjunto completo de todas las n! permutaciones posibles.

El hecho de que el algoritmo de Sattolo siempre produce un ciclo de longitud n se puede demostrar por inducción. Supongamos por inducción que después de la iteración inicial del bucle, las iteraciones restantes permutan los primeros n − 1 elementos de acuerdo con un ciclo de longitud n − 1 (esas iteraciones restantes son simplemente el algoritmo de Sattolo aplicado a esos primeros n − 1 elementos). Esto significa que al rastrear el elemento inicial hasta su nueva posición p, luego el elemento originalmente en la posición p hasta su nueva posición, y así sucesivamente, solo se regresa a la posición inicial después de haber visitado todas las demás posiciones. Supongamos que la iteración inicial intercambió el elemento final con el que estaba en la posición (no final) k, y que la permutación posterior de los primeros n − 1 elementos lo movió a la posición l; comparamos la permutación π de todos los n elementos con la permutación restante σ de los primeros n − 1 elementos. Al rastrear posiciones sucesivas como se acaba de mencionar, no hay diferencia entre π y σ hasta llegar a la posición k. Pero entonces, bajo π el elemento originalmente en la posición k se mueve a la posición final en lugar de a la posición l, y el elemento originalmente en la posición final se mueve a la posición l. A partir de ahí, la secuencia de posiciones de π vuelve a seguir la secuencia de σ, y se habrán visitado todas las posiciones antes de volver a la posición inicial, como se requiere.

En cuanto a la probabilidad igual de las permutaciones, basta observar que el algoritmo modificado implica (n−1)! secuencias posibles distintas de números aleatorios producidos, cada una de las cuales produce claramente una permutación diferente, y cada una de las cuales ocurre (suponiendo que la fuente de números aleatorios es imparcial) con igual probabilidad. Las (n−1)! permutaciones diferentes así producidas agotan precisamente el conjunto de ciclos de longitud n: cada uno de esos ciclos tiene una notación de ciclo única con el valor n en la posición final, lo que permite (n−1)! permutaciones de los valores restantes para llenar las otras posiciones de la notación de ciclo.

Un ejemplo de implementación del algoritmo de Sattolo en Python es:

desde al azar importación Randrangedef sattolo_cycle()Temas) - No. Ninguno: ""El algoritmo de Sattolo."" i = Len()Temas) mientras i ■ 1: i = i - 1 j = Randrange()i) # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 Temas[j] Temas[i] = Temas[i] Temas[j]

Se han desarrollado varios algoritmos de mezcla paralela basados en Fisher-Yates.

En 1990, Anderson desarrolló una versión paralela para máquinas con una pequeña cantidad de procesadores que accedían a la memoria compartida. El algoritmo genera permutaciones aleatorias de manera uniforme siempre que el hardware funcione de manera justa.

En 2015, Bacher et al. produjeron MERGESHUFFLE, un algoritmo que divide la matriz en bloques de tamaño aproximadamente igual, utiliza Fisher-Yates para mezclar cada bloque y luego utiliza una fusión aleatoria de forma recursiva para obtener la matriz mezclada.

La complejidad temporal y espacial asintótica de la permutación Fisher-Yates es óptima. Combinada con una fuente de números aleatorios imparcial de alta calidad, también garantiza la producción de resultados imparciales. En comparación con otras soluciones, también tiene la ventaja de que, si solo se necesita una parte de la permutación resultante, se puede detener a mitad de camino, o incluso detener y reiniciar repetidamente, generando la permutación de forma incremental según sea necesario.

El método ingenuo de intercambiar cada elemento con otro elemento elegido aleatoriamente de todos los elementos es parcial. Diferentes permutaciones tendrán diferentes probabilidades de ser generadas, para cada ${\displaystyle n confiado2}$, porque el número de diferentes permutaciones, ${\displaystyle n!}$, no divide uniformemente el número de resultados aleatorios del algoritmo, ${\displaystyle n^{n}$. En particular, por el postulado de Bertrand habrá al menos un primer número entre ${\displaystyle n/2}$ y ${\displaystyle n}$, y este número dividirá ${\displaystyle n!}$ pero no dividir ${\displaystyle n^{n}$.

desde al azar importación Randrangedef naive_shuffle()Temas) - No. Ninguno: ""Un método ingenuo. Este es un ejemplo de lo que no debe hacer: utilizar Fisher-Yates en su lugar."" n = Len()Temas) para i dentro rango()n): j = Randrange()n) # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 # 0 Temas[j] Temas[i] = Temas[i] Temas[j]

Un método alternativo asigna un número aleatorio a cada elemento del conjunto que se va a mezclar y luego ordena el conjunto según los números asignados. El método de ordenación tiene la misma complejidad temporal asintótica que Fisher-Yates: aunque la ordenación general es O(n log n), los números se ordenan de manera eficiente utilizando la ordenación por radix en un tiempo O(n). Al igual que la mezcla de Fisher-Yates, el método de ordenación produce resultados imparciales. Sin embargo, se debe tener cuidado para garantizar que los números aleatorios asignados nunca se dupliquen, ya que los algoritmos de ordenación normalmente no ordenan los elementos aleatoriamente en caso de empate. Además, este método requiere un espacio asintóticamente mayor: O(n) espacio de almacenamiento adicional para los números aleatorios, frente a O(1) espacio para la mezcla de Fisher-Yates. Por último, el método de ordenamiento tiene una implementación paralela simple, a diferencia del ordenamiento aleatorio de Fisher-Yates, que es secuencial.

Una variante del método anterior que se ha utilizado en algunos lenguajes que admiten la ordenación con funciones de comparación especificadas por el usuario es mezclar una lista ordenándola con una función de comparación que devuelve valores aleatorios. Sin embargo, es muy probable que esto produzca distribuciones altamente no uniformes, que además dependen en gran medida del algoritmo de ordenación utilizado. Por ejemplo, supongamos que se utiliza quicksort como algoritmo de ordenación, con un elemento fijo seleccionado como primer elemento pivote. El algoritmo comienza a comparar el pivote con todos los demás elementos para separarlos en aquellos menores y mayores que él, y los tamaños relativos de esos grupos determinarán el lugar final del elemento pivote. Para una permutación aleatoria distribuida uniformemente, cada posición final posible debería tener la misma probabilidad para el elemento pivote, pero si cada una de las comparaciones iniciales devuelve "menor" o "mayor" con la misma probabilidad, entonces esa posición tendrá una distribución binomial para p = 1/2, lo que da posiciones cerca del medio de la secuencia con una probabilidad mucho mayor que las posiciones cerca de los extremos. Las funciones de comparación aleatorias aplicadas a otros métodos de ordenación, como la ordenación por combinación, pueden producir resultados que parecen más uniformes, pero tampoco lo son del todo, ya que la combinación de dos secuencias eligiendo repetidamente una de ellas con la misma probabilidad (hasta que la elección se ve forzada por el agotamiento de una secuencia) no produce resultados con una distribución uniforme; en cambio, la probabilidad de elegir una secuencia debería ser proporcional al número de elementos que quedan en ella. De hecho, ningún método que utilice únicamente eventos aleatorios bidireccionales con la misma probabilidad ("lanzamiento de una moneda"), repetidos un número limitado de veces, puede producir permutaciones de una secuencia (de más de dos elementos) con una distribución uniforme, porque cada ruta de ejecución tendrá como probabilidad un número racional con una potencia de 2 como denominador, mientras que la probabilidad requerida 1/n! para cada permutación posible no es de esa forma.

En principio, este método de mezcla puede incluso dar lugar a fallos del programa, como bucles infinitos o violaciones de acceso, porque la exactitud de un algoritmo de ordenación puede depender de propiedades de la relación de ordenación (como la transitividad) que una comparación que produzca valores aleatorios seguramente no tendrá. Aunque este tipo de comportamiento no debería ocurrir con rutinas de ordenación que nunca realizan una comparación cuyo resultado se puede predecir con certeza (en base a comparaciones anteriores), puede haber razones válidas para hacer deliberadamente tales comparaciones. Por ejemplo, el hecho de que cualquier elemento deba compararse con sí mismo permite utilizarlos como valor centinela por razones de eficiencia y, si este es el caso, una función de comparación aleatoria rompería el algoritmo de ordenación.

Se debe tener cuidado al implementar la mezcla Fisher-Yates, tanto en la implementación del algoritmo en sí como en la generación de los números aleatorios en los que se basa, de lo contrario, los resultados pueden mostrar un sesgo detectable. A continuación se enumeran varias fuentes comunes de sesgo.

Un error común al implementar el barajado de Fisher-Yates es elegir números aleatorios de un rango incorrecto. El algoritmo defectuoso puede parecer que funciona correctamente, pero no producirá cada permutación posible con la misma probabilidad, y puede que no produzca ciertas permutaciones en absoluto. Por ejemplo, un error común de un dígito sería elegir que el índice j de la entrada a intercambiar en el ejemplo anterior sea siempre estrictamente menor que el índice i de la entrada con la que se intercambiará. Esto convierte el barajado de Fisher-Yates en el algoritmo de Sattolo, que produce solo permutaciones que consisten en un solo ciclo que involucra a todos los elementos: en particular, con esta modificación, ningún elemento de la matriz puede terminar nunca en su posición original.

De manera similar, seleccionar siempre j de todo el rango de índices válidos de matriz en cada iteración también produce un resultado sesgado, aunque de manera menos obvia. Esto se puede ver por el hecho de que al hacerlo se obtienen nⁿ posibles secuencias distintas de intercambios, mientras que solo hay n! permutaciones posibles de una matriz de n-elementos. Dado que nⁿ nunca puede ser divisible de manera exacta por n! cuando n > 2 (ya que este último es divisible por n−1, que no comparte factores primos con n), algunas permutaciones deben ser producidas por más de las nⁿ secuencias de intercambios que otras. Como 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 permutaciones posibles de esta matriz (3! = 6), pero el algoritmo produce 27 mezclas posibles (3³ = 27). En este caso, [1, 2, 3], [3, 1, 2] y [3, 2, 1] resultan cada uno de 4 de las 27 mezclas, mientras que cada una de las 3 permutaciones restantes ocurre en 5 de las 27 mezclas.

La matriz de la derecha muestra la probabilidad de que cada elemento de una lista de longitud 7 termine en cualquier otra posición. Observe que, para la mayoría de los elementos, terminar en su posición original (la diagonal principal de la matriz) tiene la probabilidad más baja, y moverse una posición hacia atrás tiene la probabilidad más alta.

Para realizar una mezcla de Fisher-Yates se deben seleccionar números enteros aleatorios distribuidos uniformemente de varios rangos. Sin embargo, la mayoría de los generadores de números aleatorios (ya sean verdaderos o pseudoaleatorios) solo proporcionarán directamente números en un rango fijo de 0 a RAND_MAX y, en algunas bibliotecas, RAND_MAX puede ser tan bajo como 32767. Una forma simple y comúnmente utilizada de forzar dichos números dentro de un rango deseado es aplicar el operador módulo; es decir, dividirlos por el tamaño del rango y tomar el resto. Sin embargo, la necesidad de una mezcla de Fisher-Yates de generar números aleatorios en cada rango de 0–1 a 0–n casi garantiza que algunos de estos rangos no dividirán uniformemente el rango natural del generador de números aleatorios. Por lo tanto, los restos no siempre estarán distribuidos uniformemente y, peor aún, el sesgo estará sistemáticamente a favor de los restos pequeños.

Por ejemplo, supongamos que la fuente de números aleatorios que utilizamos arroja números del 0 al 99 (como era el caso de las tablas originales de Fisher y Yates), que son 100 valores, y que deseamos obtener un número aleatorio imparcial del 0 al 15 (16 valores). Si simplemente dividimos los números por 16 y tomamos el resto, descubriremos que los números del 0 al 3 aparecen aproximadamente un 17 % más a menudo que los demás. Esto se debe a que 16 no divide exactamente a 100: el mayor múltiplo de 16 menor o igual a 100 es 6×16 = 96, y son los números en el rango incompleto 96-99 los que causan el sesgo. La forma más sencilla de solucionar el problema es descartar esos números antes de tomar el resto y volver a intentarlo hasta que aparezca un número en el rango adecuado. Si bien en principio esto podría, en el peor de los casos, tardar una eternidad, el número esperado de reintentos siempre será menor que uno.

En 2018, Daniel Lemire describió un método para obtener números aleatorios en los rangos requeridos que es imparcial y casi nunca realiza la costosa operación módulo.

Un problema relacionado ocurre con las implementaciones que primero generan un número aleatorio de punto flotante (normalmente en el rango [0,1]) y luego lo multiplican por el tamaño del rango deseado y lo redondean hacia abajo. El problema aquí es que los números aleatorios de punto flotante, por más cuidadosos que sean, siempre tienen una precisión finita. Esto significa que solo hay un número finito de posibles valores de punto flotante en cualquier rango dado, y si el rango se divide en una cantidad de segmentos que no divide este número de manera uniforme, algunos segmentos terminarán con más valores posibles que otros. Si bien el sesgo resultante no mostrará la misma tendencia sistemática a la baja que en el caso anterior, seguirá estando presente.

El costo adicional de eliminar el "sesgo de módulo" al generar números enteros aleatorios para una mezcla de Fisher-Yates depende del enfoque (módulo clásico, multiplicación de punto flotante o multiplicación de números enteros de Lemire), el tamaño de la matriz que se va a mezclar y el generador de números aleatorios utilizado.

Un problema adicional surge cuando se utiliza la mezcla Fisher-Yates con un generador de números pseudoaleatorios o PRNG: como la secuencia de números que genera dicho generador está completamente determinada por su estado interno al comienzo de la secuencia, una mezcla impulsada por dicho generador no puede producir más permutaciones distintas que estados posibles distintos que tiene el generador. Incluso cuando el número de estados posibles excede el número de permutaciones, la naturaleza irregular de la asignación de secuencias de números a permutaciones significa que algunas permutaciones ocurrirán con más frecuencia que otras. Por lo tanto, para minimizar el sesgo, el número de estados del PRNG debe exceder el número de permutaciones en al menos varios órdenes de magnitud.

Por ejemplo, el generador de números pseudoaleatorios incorporado que proporcionan muchos lenguajes de programación y/o bibliotecas puede tener a menudo solo 32 bits de estado interno, lo que significa que solo puede producir 2³² secuencias de números diferentes. Si se utiliza un generador de este tipo para barajar una baraja de 52 cartas, solo puede producir una fracción muy pequeña de las 52! ≈ 2^225,6 permutaciones posibles. Es imposible que un generador con menos de 226 bits de estado interno produzca todas las permutaciones posibles de una baraja de 52 cartas.

Ningún generador de números pseudoaleatorios puede producir más secuencias distintas, a partir del punto de inicialización, que valores de semilla distintos con los que puede inicializarse. Por lo tanto, un generador que tiene 1024 bits de estado interno pero que se inicializa con una semilla de 32 bits todavía puede producir sólo 2³² permutaciones diferentes justo después de la inicialización. Puede producir más permutaciones si se ejercita el generador una gran cantidad de veces antes de comenzar a usarlo para generar permutaciones, pero esta es una forma muy ineficiente de aumentar la aleatoriedad: suponiendo que uno puede disponer el uso del generador de un número aleatorio de hasta mil millones, digamos 2³⁰ para simplificar, veces entre la inicialización y la generación de permutaciones, entonces el número de permutaciones posibles sigue siendo sólo 2⁶².

Otro problema surge cuando se utiliza un generador de números aleatorios lineal congruente simple con el método de división y toma de resto de reducción de rango descrito anteriormente. El problema aquí es que los bits de orden inferior de un generador de números aleatorios lineal congruente con módulo 2^e son menos aleatorios que los de orden superior: los bits de orden inferior n del generador tienen un período de como máximo 2ⁿ. Cuando el divisor es una potencia de dos, tomar el resto significa esencialmente descartar los bits de orden superior, de modo que uno termina con un valor significativamente menos aleatorio. Se aplican reglas diferentes si el generador de números aleatorios lineales tiene módulo primo, pero estos generadores son poco comunes. Este es un ejemplo de la regla general de que un generador de números aleatorios o un generador de números aleatorios de mala calidad producirán barajas de mala calidad.

• Permutación, El shuffle de los Fisher-Yates no depende de los elementos que se están escupiendo. Las propiedades de las permutaciones del conjunto estándar ${\displaystyle S=\{1,2,\ldotsn}$ han sido ampliamente estudiados.
• RC4, un cifer de flujo basado en el enjuague de un array
• Muestra de reserva, en particular Algorithm R, que es una especialización de los arbustos Fisher-Yates

• Un ejemplo interactivo Mike Bostock proporciona ejemplos en JavaScript con visualizaciones que muestran cómo el moderno (Durstenfeld) Fisher-Yates shuffle es más eficiente que otros shuffles.

  El ejemplo incluye el enlace a un diagrama de matriz que ilustra cómo Fisher-Yates es imparcial mientras que el método ingenuo (selecciona) naïve swap i -> random) es parcial. Seleccione Fisher-Yates y cambiar la línea para tener predecremento --m más que después de la sentencia m-- dar i = Math.floor(Math.random() * --m);, y usted consigue el algoritmo de Sattolo donde ningún artículo permanece en su posición original.