El algoritmo de barajado de Fisher-Yates es un algoritmo para barajar una secuencia finita . El algoritmo toma una lista de todos los elementos de la secuencia y determina continuamente el siguiente elemento de la secuencia barajada extrayendo aleatoriamente un elemento de la lista hasta que no quede ningún elemento. [1] 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 barajan y los baraja en su lugar .
El barajado de Fisher-Yates recibe su nombre de Ronald Fisher y Frank Yates , quienes lo describieron por primera vez. También se lo conoce como barajado de Knuth , en honor a Donald Knuth . [2] Se puede utilizar una variante del barajado de Fisher-Yates, conocida como algoritmo de Sattolo , 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 . [3] En su descripción del algoritmo utilizaron 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:
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 del 1 al 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ñada para uso informático, fue introducida por Richard Durstenfeld en 1964 [4] y popularizada por Donald E. Knuth en The Art of Computer Programming como "Algorithm P (Shuffling)". [5] Ni el artículo de Durstenfeld ni la primera edición de Knuth de The Art of Computer Programming reconocieron el trabajo de Fisher y Yates; es posible que no estuvieran al tanto de él. [ cita requerida ] Las ediciones posteriores de The Art of Computer Programming de Knuth mencionan la contribución de Fisher y Yates. [6]
El algoritmo descrito por Durstenfeld es más eficiente que el propuesto por Fisher y Yates: mientras que una implementación informática ingenua del método de Fisher y Yates perdería tiempo innecesariamente contando los números restantes en el paso 3 anterior, la solución de Durstenfeld es mover los números "tachados" al final de la lista intercambiándolos con el último número no tachado en cada iteración. Esto reduce la complejidad temporal del algoritmo en comparación con la implementación ingenua. [7] Este cambio da como resultado el siguiente algoritmo (para una matriz de base cero ).
-- Para mezclar una matriz a de n elementos (índices 0.. n -1): para i desde n −1 hasta 1, haga j ← entero aleatorio tal que 0 ≤ j ≤ i intercambie 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 mezclar una matriz a de n elementos (índices 0.. n -1): para i desde 0 hasta n −2 hacemos j ← entero aleatorio tal que i ≤ j < n intercambiamos 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 elige un número aleatorio j entre 1 y 8. Si , por ejemplo, j = 3, se tacha la tercera letra del cuaderno y se anota 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 tachado 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 completar la permutación:
Después de ocho pasos, el algoritmo está completo y la permutación resultante es GEDCAHB F.
Este ejemplo muestra una implementación simple en Python de la mezcla Fisher-Yates.
importar aleatorio definición barajar ( n ): números = lista ( rango ( n )) barajado = [] mientras que números : k = aleatorio . randint ( 0 , len ( números ) - 1 ) barajado.add ( números [ k ] ) números . pop ( k ) volver barajadoLa 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 . En caso de que la posición aleatoria sea la número i , este "movimiento" (al mismo lugar) involucra un valor no inicializado, pero eso no importa, ya que el valor se sobrescribe inmediatamente. No se necesita una inicialización separada y no se realiza ningún intercambio. En el caso común donde la fuente se define por alguna función simple, como los números enteros de 0 a n − 1, la fuente simplemente se puede reemplazar con la función ya que la fuente nunca se altera durante la ejecución.
Para inicializar una matriz a de n elementos en una copia aleatoriamente mezclada de source , ambas basadas en 0: para i de 0 a n − 1 hacer j ← entero aleatorio tal que 0 ≤ j ≤ i si j ≠ i a [ i ] ← a [ j ] a [ j ] ← source [ i ]
Se puede ver que la mezcla de adentro hacia afuera es correcta por inducción . Suponiendo un generador de números aleatorios perfecto, cada una de las n ! secuencias diferentes de números aleatorios que podrían obtenerse de las llamadas de random producirá una permutación diferente de los valores, por lo que todos estos se obtienen exactamente una vez. La condición que verifica si j ≠ i puede omitirse en lenguajes que no tienen problemas para acceder a valores de matriz no inicializados. Esto elimina n ramas condicionales a un costo esperado de H n ≈ ln n + γ asignaciones redundantes.
Otra ventaja de esta técnica 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, se construye la matriz a de forma iterativa a partir de un valor vacío, y un .length representa el número actual de elementos vistos.
Para inicializar una matriz vacía a en una copia aleatoria de source cuya longitud no se conoce: while source .moreDataAvailable j ← entero aleatorio tal que 0 ≤ j ≤ a .length if j = a .length a .append( source .next) else a .append( a [ j ]) a [ j ] ← source .next
En 1986 Sandra Sattolo publicó un algoritmo muy similar para generar ciclos distribuidos uniformemente de longitud (máxima) n . [8] [9] 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 e i −1 (en lugar de entre 1 e 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 está en la posición (no final) k , y que la permutación posterior de los primeros n − 1 elementos luego lo movió a la posición l ; comparamos la permutación π de todos los n elementos con esa permutación restante σ de los primeros n − 1 elementos. Si se trazan posiciones sucesivas como se acaba de mencionar, no hay diferencia entre π y σ hasta llegar a la posición k . Pero entonces, bajo π el elemento que originalmente estaba en la posición k se mueve a la posición final en lugar de a la posición l , y el elemento que originalmente estaba en la posición final se mueve a la posición l . A partir de ahí, la secuencia de posiciones para π sigue de nuevo la secuencia para σ , 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)! distintas secuencias posibles de números aleatorios producidos, cada una de las cuales produce claramente una permutación diferente, y cada una de las cuales ocurre (asumiendo que la fuente de números aleatorios es imparcial) con igual probabilidad. Las ( n −1)! distintas permutaciones 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.
Una implementación de ejemplo del algoritmo de Sattolo en Python es:
de importación aleatoria randrange def sattolo_cycle ( items ) -> None : """Algoritmo de Sattolo.""" i = len ( items ) while i > 1 : i = i - 1 j = randrange ( i ) # 0 <= j <= i-1 items [ j ], items [ i ] = items [ i ], items [ 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 acceden a la memoria compartida. [10] 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. [11]
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 sesgado. [12] Diferentes permutaciones tendrán diferentes probabilidades de ser generadas, para cada , porque el número de diferentes permutaciones, , no divide de manera uniforme el número de resultados aleatorios del algoritmo, . En particular, por el postulado de Bertrand habrá al menos un número primo entre y , y este número dividirá pero no dividirá a .
de importación aleatoria randrange def naive_shuffle ( items ) -> None : """Un método ingenuo. Este es un ejemplo de lo que no se debe hacer: utilice Fisher-Yates en su lugar.""" n = len ( items ) for i in range ( n ): j = randrange ( n ) # 0 <= j <= n-1 items [ j ], items [ i ] = items [ i ], items [ j ] Un método alternativo asigna un número aleatorio a cada elemento del conjunto que se va a barajar y luego ordena el conjunto según los números asignados. El método de ordenamiento tiene la misma complejidad temporal asintótica que Fisher-Yates: aunque el ordenamiento general es O ( n log n ), los números se ordenan de manera eficiente utilizando el ordenamiento por radix en tiempo O ( n ). Al igual que el barajado de Fisher-Yates, el método de ordenamiento 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 ordenamiento normalmente no ordenan los elementos aleatoriamente en caso de empate. [13] 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 el barajado de Fisher-Yates. Finalmente, el método de ordenamiento tiene una implementación paralela simple , a diferencia del barajado de Fisher-Yates, que es secuencial.
Una variante del método anterior que ha tenido cierto uso en lenguajes que admiten la ordenación con funciones de comparación especificadas por el usuario es barajar 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. [14] [15] 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 ser igualmente probable para el elemento pivote, pero si cada una de las comparaciones iniciales devuelve "menor" o "mayor" con igual 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 fusión pueden producir resultados que parecen más uniformes, pero tampoco lo son del todo, ya que fusionar dos secuencias eligiendo repetidamente una de ellas con igual 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 [ cita requerida ] . De hecho, ningún método que utilice solo eventos aleatorios bidireccionales con igual probabilidad ( "lanzamiento de 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 como denominador una potencia de 2 , mientras que la probabilidad requerida 1/ n ! para cada permutación posible no es de esa forma [ cita requerida ] .
En principio, este método de barajado puede incluso dar lugar a fallos del programa, como bucles infinitos o violaciones de acceso, porque la corrección de un algoritmo de ordenación puede depender de propiedades de la relación de orden (como la transitividad ) que una comparación que produzca valores aleatorios ciertamente no tendrá. [16] 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 previas), puede haber razones válidas para hacer deliberadamente tales comparaciones. Por ejemplo, el hecho de que cualquier elemento deba compararse igual a sí mismo permite usarlos 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 el barajado 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 los 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 de matriz válidos 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 n posibles secuencias distintas de intercambios, mientras que solo hay n ! permutaciones posibles de una matriz de n elementos. Dado que n n nunca puede ser divisible de manera uniforme 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 n secuencias de intercambios que otras. Como ejemplo concreto de este sesgo, observe la distribución de los posibles resultados de barajar una matriz de tres elementos [1, 2, 3]. Hay 6 posibles permutaciones de esta matriz (3! = 6), pero el algoritmo produce 27 barajadas posibles (3 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. [17] Una forma simple y comúnmente utilizada de forzar dichos números en un rango deseado es aplicar el operador módulo ; [18] es decir, dividirlos por el tamaño del rango y tomar el resto. Sin embargo, la necesidad en 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 se distribuirán uniformemente y, peor aún, el sesgo estará sistemáticamente a favor de los restos pequeños. [19] [19] : Módulo clásico (sesgado)
Por ejemplo, supongamos que la fuente de números aleatorios que utilizamos arroja números del 0 al 99 (como en 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. [20] Aunque 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. [21]
Un problema relacionado ocurre con las implementaciones que primero generan un número aleatorio de punto flotante (generalmente en el rango [0,1]) y luego lo multiplican por el tamaño del rango deseado y lo redondean hacia abajo. [19] : FP Multiply (Biased) [21] : 2 El problema aquí es que los números aleatorios de punto flotante, por más cuidado que se generen, siempre tienen solo 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 descendente sistemática que en el caso anterior, seguirá estando allí.
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 a mezclar y el generador de números aleatorios utilizado. [19] : Evaluación comparativa ...
Un problema adicional ocurre 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. [22] 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 a menudo puede tener solo 32 bits de estado interno, lo que significa que solo puede producir 2 32 secuencias diferentes de números. 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. [23] 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 semilla distintos con los que puede inicializarse. [24] Por lo tanto, un generador que tiene 1024 bits de estado interno pero que se inicializa con una semilla de 32 bits todavía solo puede producir 2 32 permutaciones diferentes justo después de la inicialización. Puede producir más permutaciones si uno 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 30 para simplificar, veces entre la inicialización y la generación de permutaciones, entonces el número de permutaciones posibles sigue siendo solo 2 62 .
Otro problema surge cuando se utiliza un PRNG lineal congruente simple con el método de división y toma resto de reducción de rango descrito anteriormente. El problema aquí es que los bits de orden bajo de un PRNG lineal congruente con módulo 2 e son menos aleatorios que los de orden alto: [6] los bits bajos n del generador tienen un período de como máximo 2 n . Cuando el divisor es una potencia de dos, tomar el resto significa esencialmente descartar los bits de orden alto, de modo que uno termina con un valor significativamente menos aleatorio. Se aplican reglas diferentes si el LCG tiene módulo primo, pero tales generadores son poco comunes. Este es un ejemplo de la regla general de que un RNG o PRNG de mala calidad producirá barajas de mala calidad.
El ejemplo incluye un enlace a un diagrama de matriz que ilustra cómo Fisher-Yates es imparcial mientras que el método ingenuo (select naïve swap i -> random) es sesgado. Seleccione Fisher-Yatesy cambie la línea para que tenga un decremento previo --men lugar de uno posterior , m--lo que da como resultado i = Math.floor(Math.random() * --m);, y obtendrá el algoritmo de Sattolo, donde ningún elemento permanece en su posición original.
