Fisher-Yates Shuffle (llamado así por Ronald Fisher y Frank Yates , también conocido como Knuth Shuffle (por Donald Knuth ), es un algoritmo para generar permutaciones aleatorias de un conjunto finito , en pocas palabras, para barajar aleatoriamente un conjunto. Una variante de Fisher-Yates El barajado de Yates, conocido como el algoritmo de Sattolo , se puede utilizar para generar un ciclo aleatorio de permutaciones de longitud n . Un algoritmo de barajado de Fisher-Yates correctamente implementado es imparcial , de modo que cada permutación se genera con la misma probabilidad. La versión actual del El algoritmo es muy eficiente y toma un tiempo proporcional a la cantidad de elementos en el conjunto, y no requiere memoria adicional.
El procedimiento básico de barajar de Fisher-Yates es similar a sacar al azar billetes con números de un sombrero o cartas de una baraja, un elemento tras otro, hasta que se agoten los elementos. El algoritmo proporciona un método eficiente y riguroso para tales operaciones, garantizando un resultado imparcial.
El barajado de Fisher-Yates, en su forma original, fue descrito en 1938 por Ronald Fisher y Frank Yates en su libro Statistical Tables for Research in Biology, Architecture, and Medicine [1] (La última edición del libro describe un algoritmo de barajado diferente atribuido a C. R. Rao .) Su método fue desarrollado para lápiz y papel y utilizó tablas precalculadas de números aleatorios como fuente de aleatoriedad. Se veía así:
Si los números usados en el paso 2 son realmente aleatorios y no sesgados, entonces obtenemos las mismas permutaciones aleatorias (aleatorias y no sesgadas). Fisher y Yates describieron cómo obtener dichos números aleatorios para cualquier intervalo y proporcionaron tablas para evitar sesgos. También imaginaron la posibilidad de simplificar el método, eligiendo números aleatorios de uno a N y luego descartando repeticiones, para generar la mitad de la permutación generada, y solo luego usar un algoritmo más complejo para la mitad restante, de lo contrario, también aparecerán números repetidos. con frecuencia.
Una versión moderna del algoritmo aleatorio de Fisher-Yates para uso en computadoras fue presentada por Richard Durstenfeld en 1964 en Communications of the ACM Volume 7, Issue 7, titulada "Algorithm 235: Random permutation" [2] , y fue popularizada por Donald Knuth en el segundo volumen de su libro El Arte de Programar como Algoritmo P [3] . Ni Durstenfeld ni Knuth mencionaron el algoritmo de Fisher y Yates en la primera edición del libro, y parece que no lo conocían. Sin embargo, en la segunda edición de El arte de la programación, se corrigió esta omisión [4]
El algoritmo descrito por Durstenfeld difiere del algoritmo de Fisher y Yates en detalles pequeños pero significativos. Para evitar que la implementación informática del algoritmo pierda tiempo iterando los números restantes en el paso 3, los números elegidos por Durstenfeld se transfirieron al final de la lista en cada iteración permutando con el último número no seleccionado. Esta modificación redujo la complejidad temporal del algoritmo a O ( n ), en comparación con O ( n 2 ) del algoritmo original [5] . Este cambio conduce al siguiente algoritmo.
Para mezclar una matriz a de n elementos (índices 0..n-1): para todos los i de n − 1 a 1 , ejecute j ← número aleatorio 0 ≤ j ≤ i swap a [ j ] y a [ i ]El shuffle de Fischer-Yates en la variante de Durstenfeld es un shuffle in place . Es decir, cuando se le da una matriz completa, mezcla los elementos de la misma matriz en lugar de crear una copia de la matriz con los elementos reorganizados. Esto puede brindar una ventaja significativa cuando se mezclan arreglos grandes.
Inicializar y mezclar una matriz al mismo tiempo puede aumentar ligeramente la eficiencia si utiliza la versión "invertida" de la reproducción aleatoria. En esta versión, el elemento original en el índice i se mueve a una posición aleatoria entre las primeras i posiciones después de que el elemento se mueva de esa posición a la posición i . En el caso de elegir un número aleatorio igual a i , primero se transferirá el valor no asignado, pero inmediatamente se sobrescribirá con el valor correcto. No se necesita una inicialización separada en esta variante y no se realizan permutaciones. Si la fuente se define mediante una función simple, como los números enteros de 0 a n - 1 , la fuente puede reemplazarse simplemente por esa función, ya que la fuente nunca cambia en tiempo de ejecución.
Para crear una matriz a a partir de n elementos fuente mezclados aleatoriamente : para i de 0 a n − 1 do j ← entero aleatorio con 0 ≤ j ≤ i a [ i ] ← a [ j ] a [ j ] ← source [ i ]La corrección de la reproducción aleatoria "invertida" puede probarse por inducción; cualquiera de n ! diferentes secuencias de números aleatorios obtenidos durante la operación del algoritmo forman su propia permutación, de modo que todas las permutaciones se recibirán una sola vez.
Otra ventaja de este enfoque es que sin siquiera conocer el número "n", el número de elementos de la fuente , podemos crear permutaciones uniformemente distribuidas. Debajo de la matriz a se crea iterativamente comenzando desde vacío y .length representa su longitud actual.
while source .iselther j ← número aleatorio 0 ≤ j ≤ a .length si j = a .length a .add( source .nextItem) de lo contrario a .add( a [ j ]) a [ j ] ← source .nextItemComo ejemplo, reorganicemos los números del 1 al 8 usando el método original de Fisher-Yates . Primero, escribamos los números en papel:
| Intervalo | Seleccionado | Reclutar | Resultado |
|---|---|---|---|
| 1 2 3 4 5 6 7 8 |
Ahora tomemos un número aleatorio k del 1 al 8, que sea 3, y tachemos el número k (es decir, el tercero) (3, por supuesto) y transfiéralo a la secuencia resultante:
| Intervalo | Seleccionado | Reclutar | Resultado |
|---|---|---|---|
| 1-8 | 3 | 1 2 3 4 5 6 7 8 | 3 |
Ahora seleccionamos un segundo número aleatorio, esta vez del intervalo 1-7, que sea el 4. Ahora tachamos el cuarto número que aún no ha sido tachado del borrador -este será el número 5- y lo sumamos al resultado:
| Intervalo | Seleccionado | Reclutar | Resultado |
|---|---|---|---|
| 1-7 | cuatro | 1 2 3 4 5 6 7 8 | 3 5 |
Ahora elegimos un número aleatorio del intervalo 1-6, luego del intervalo 1-5, y así sucesivamente, repitiendo el proceso de tachado como se describió anteriormente:
| Intervalo | Seleccionado | Reclutar | Resultado |
|---|---|---|---|
| 1-6 | 5 | 1 2 3 4 5 6 7 8 | 3 5 7 |
| 1-5 | 3 | 1 2 3 4 5 6 7 8 | 3 5 7 4 |
| 1-4 | cuatro | 1 2 3 4 5 6 7 8 | 3 5 7 4 8 |
| 1-3 | una | 1 2 3 4 5 6 7 8 | 3 5 7 4 8 1 |
| 1-2 | 2 | 1 2 3 4 5 6 7 8 | 3 5 7 4 8 1 6 |
| 1 2 3 4 5 6 7 8 | 3 5 7 4 8 1 6 2 |
Hagamos lo mismo con el método Durstenfeld . Esta vez, en lugar de tachar los números seleccionados y copiarlos en algún lugar, los reorganizamos con los números aún no seleccionados. Como antes, comenzamos escribiendo los números del 1 al 8:
| Intervalo | Seleccionado | Reclutar | Resultado |
|---|---|---|---|
| 1 2 3 4 5 6 7 8 |
Elijamos el primer número aleatorio del 1 al 8, digamos que es 6, así que intercambiemos los números 6 y 8 de la lista:
| Intervalo | Seleccionado | Reclutar | Resultado |
|---|---|---|---|
| 1-8 | 6 | 1 2 3 4 5 8 7 | 6 |
Seleccionamos el siguiente número aleatorio del intervalo 1 - 7, y dejamos que sea 2. Ahora intercambiamos los números 2 y 7:
| Intervalo | Seleccionado | Reclutar | Resultado |
|---|---|---|---|
| 1-7 | 2 | 1 7 3 4 5 8 | 26 _ |
Elegimos el siguiente número aleatorio del intervalo 1 - 6, y dejamos que sea 6, lo que significa que debemos dejar el sexto número en su lugar (después de las permutaciones anteriores, el número 8 está aquí). Seguimos actuando de esta forma hasta formar toda la permutación:
| Intervalo | Seleccionado | Reclutar | Resultado |
|---|---|---|---|
| 1-6 | 6 | 1 7 3 4 5 | 8 2 6 |
| 1-5 | una | 5 7 3 4 | 1 8 2 6 |
| 1-4 | 3 | 5 7 4 | 3 1 8 2 6 |
| 1-3 | 3 | 5 7 | 4 3 1 8 2 6 |
| 1-2 | una | 7 | 5 4 3 1 8 2 6 |
Sandra Sattolo publicó un algoritmo muy similar en 1986 para generar ciclos uniformemente distribuidos de longitud (máxima) n [6] La diferencia entre los algoritmos de Durstenfeld y Sattolo está solo en el paso 2: en el algoritmo de Sattolo, se selecciona un número aleatorio j de el intervalo 1 - i −1, no de 1 - i . Esta simple modificación da como resultado permutaciones que consisten en un solo ciclo.
De hecho, como se describe a continuación, es fácil implementar accidentalmente el algoritmo de Sattolo al intentar crear el algoritmo de Fisher-Yates. ¡ Tal error conduce a la generación de permutaciones a partir de un conjunto más pequeño ( n − 1)! ciclos de longitud N , en lugar de un conjunto completo de n ! posibles permutaciones.
Que el algoritmo de Suttolo siempre crea un ciclo de longitud n puede demostrarse por inducción. Suponga que después de la primera iteración (que movió el elemento n a la − 1.nformaron un ciclo de elementos de longitudrestantesn)n<kposición De acuerdo con la suposición aceptada, llegaremos a la posición inicial solo pasando por todas las demás posiciones. El último elemento, luego de moverse a la posición k , y permutaciones sucesivas de los primeros n − 1 elementos, terminará en la posición l ; compare la permutación π de todos los n elementos con la permutación σ de los primeros n − 1 elementos. Haciendo un seguimiento de las permutaciones como se mencionó anteriormente, no encontraremos la diferencia entre π y σ hasta que lleguemos a la posición k . En π , el elemento en la posición k se moverá a la última posición, no a la posición l , y el elemento en la última posición irá a la posición l . A partir de este punto, la secuencia de movimientos de los elementos π volverá a coincidir con σ , y se recorrerán todas las posiciones antes de volver a la posición inicial, según se requiera.
Como en el caso de probar la equiprobabilidad de las permutaciones, ¡es suficiente mostrar que el algoritmo de Sattolo crea ( n − 1)! diferentes permutaciones que, debido a la supuesta falta de sesgo del generador de números aleatorios, tienen la misma probabilidad. ( n − 1)! diferentes permutaciones generadas por el algoritmo cubren exactamente el conjunto de ciclos de longitud n .
Una implementación simple de Python del algoritmo de Sattolo :
de randrange de importación aleatoria def sattoloCycle ( elementos ): i = len ( elementos ) while i > 1 : i = i - 1 j = randrange ( i ) # 0 <= j <= i-1 elementos [ j ], elementos [ i ] = elementos [ i ], elementos [ j ] volverEl algoritmo de Fisher-Yates es bastante eficiente, y más aún, su velocidad y costos de memoria son asintóticamente óptimos. Cuando se utiliza un generador de números aleatorios imparcial de alta calidad, el algoritmo garantiza un resultado imparcial. El algoritmo tiene una ventaja más: si se requiere obtener alguna parte de las permutaciones, el algoritmo puede detenerse a la mitad o incluso detenerse y reanudarse muchas veces.
Existe un método alternativo: a cada elemento del conjunto se le asigna un número aleatorio y luego el conjunto se ordena de acuerdo con los números asignados. La estimación de velocidad asintótica para la clasificación es O ( n log n ) en el mejor de los casos , que es incomparable con la estimación de velocidad O ( n ) del algoritmo de Fisher-Yates. Al igual que la combinación aleatoria de Fisher-Yates, el método de clasificación produce permutaciones imparciales, pero es menos sensible a posibles problemas con el generador de números aleatorios. Sin embargo, se debe tener especial cuidado en generar números aleatorios para evitar repeticiones, ya que un algoritmo ordenado, en general, no ordena los elementos aleatoriamente.
Existe una variante del método de ordenación, en la que la lista se ordena mediante una función de comparación que devuelve un número aleatorio. Sin embargo, este es un método excepcionalmente pobre : es muy probable que forme una distribución no uniforme, además de depender del método de clasificación utilizado [7] [8] . Por ejemplo, al usar quicksort , con un elemento fijo usado como elemento de inicio. Este algoritmo de clasificación compara los elementos restantes de la lista con el seleccionado (menor o mayor que él) y de esta manera se determina la posición resultante del elemento. Si la comparación devuelve "menor que" y "mayor que" con la misma probabilidad, entonces el elemento seleccionado estará en el centro con una probabilidad mucho mayor que en los extremos. Otro método de clasificación, como merge sort , puede producir permutaciones con una probabilidad más uniforme, pero aún tiene inconvenientes porque fusionar dos secuencias con una selección aleatoria de una secuencia con la misma probabilidad (hasta que nos quedemos sin una secuencia de números aleatorios) no funciona. producir un resultado con una distribución de probabilidad uniforme, ya que la probabilidad de elegir una secuencia debe ser proporcional al número de elementos en la secuencia. De hecho, ningún método de "lanzamiento de moneda", es decir, la selección consecutiva de dos posibilidades, puede crear permutaciones (de más de dos elementos) con una distribución uniforme, ya que cualquier evento bajo este esquema tiene una probabilidad en forma de fracción racional con una divisor igual a la potencia dos, mientras que la probabilidad requerida debe ser 1/ n !.
En principio, estos métodos de barajado pueden dar lugar a un bucle de algoritmo o a un error de acceso a la memoria, ya que la corrección del algoritmo de clasificación puede depender de propiedades de ordenación como la transitividad [9] . Aunque este tipo de comportamiento no debería ocurrir en clases en las que la comparación no se puede predecir a partir de comparaciones anteriores, a veces hay razones para tales comparaciones. Por ejemplo, el hecho de que un elemento siempre deba ser igual a sí mismo, en aras de la eficiencia, puede usarse como una especie de señal o bandera, y esto, en caso de comparaciones aleatorias, viola el algoritmo de clasificación.
Se debe tener cuidado al implementar el algoritmo de Fisher-Yates, tanto en términos del propio algoritmo como en términos del generador de números aleatorios en el que se basa. A continuación se enumeran algunos errores comunes de implementación.
Un error común al implementar la combinación aleatoria de Fisher-Yates es elegir números aleatorios del intervalo incorrecto [10] . Puede parecer que un algoritmo defectuoso funciona correctamente, pero no crea todas las permutaciones posibles con la misma probabilidad, y es posible que algunas permutaciones no se creen en absoluto. Por ejemplo, puede ocurrir un error general de subestimación o sobreestimación cuando se elige el índice j del elemento que se va a intercambiar en el ejemplo anterior , siempre es menor que el índice i con el que se va a intercambiar el elemento. Como resultado, en lugar de la combinación aleatoria de Fisher-Yates, obtenemos el algoritmo de Sattolo , que forma permutaciones que afectan a todos los elementos. En particular, en este caso, ningún elemento puede estar en la posición inicial.
De manera similar, elegir j de todos los índices en la matriz en cada iteración también forma permutaciones no equiprobables, aunque no tan obvias. Esto se puede determinar por el hecho de que dicha implementación produce n n intercambios de elementos diferentes, mientras que solo hay n ! posibles permutaciones de un arreglo de n elementos. ¡ Porque n n nunca puede ser divisible por n ! sin resto para n > 2 (porque n ! es divisible por n − 1, que no tiene divisores primos comunes con n ), algunas permutaciones deben aparecer con más frecuencia que otras. Considere un ejemplo específico de permutaciones de tres elementos [1, 2, 3]. Hay 6 permutaciones posibles de este conjunto (3! = 6), pero el algoritmo genera 27 permutaciones (3 3 = 27). En este caso, [1, 2, 3], [3, 1, 2] y [3, 2, 1] ocurren 4 veces cada uno en 27 mezclas, mientras que los 3 restantes ocurren 5 veces cada uno.
La matriz de la derecha muestra la probabilidad de que cada elemento de la lista de longitud 7 aparezca en la posición final. Tenga en cuenta que para la mayoría de los elementos, permanecer en su posición original (la diagonal principal de la matriz) mientras se baraja tiene una probabilidad mínima y moverse una posición hacia la izquierda tiene una probabilidad máxima.
El algoritmo de Fisher-Yates utiliza una muestra de números aleatorios distribuidos uniformemente de varios rangos. Sin embargo, la mayoría de los generadores de números aleatorios , tanto los verdaderos aleatorios como los pseudoaleatorios, dan números en un rango fijo, digamos de 0 a 2 32 −1. Un método simple y comúnmente usado para reducir tales números al intervalo deseado es usar el resto de la división por el límite superior. La necesidad de generar números aleatorios en todos los intervalos de 0-1 a 0- n asegura que algunos de estos límites no dividirán el límite natural del generador de manera uniforme. Como resultado, la distribución no será uniforme y pequeños residuos ocurrirán con mayor frecuencia.
Suponga, por ejemplo, que el generador produce números aleatorios entre 0 y 99 (como lo hicieron Fisher y Yates en sus hojas de cálculo originales), y usted quiere números aleatorios entre 0 y 15. Si simplemente encuentra el resto de un número cuando lo divide por 16 , encontrará que los números 0-3 ocurren un 17% más a menudo que el resto. La razón de esto es que 16 no divide 100 de manera uniforme: el mayor múltiplo de 16 que no excede 100 es 6x16 = 96, y los números restantes en el rango 96-99 crean desigualdad. La forma más fácil de evitar este problema es descartar esos números antes de tomar el resto. Aunque, en principio, pueden aparecer números de dicho intervalo, la expectativa matemática del número de reintentos siempre es menor que uno.
Un problema similar ocurre cuando se usa un generador de números aleatorios que produce números de punto flotante , generalmente en el rango [0,1). El número resultante se multiplica por el tamaño del rango deseado y se redondea. El problema aquí es que incluso los números de punto flotante aleatorios generados cuidadosamente tienen una precisión finita, lo que significa que solo puede obtener un número finito de posibles números de punto flotante y, como en el caso anterior, estos números se dividen en segmentos que no dividen el número. es un número entero y algunos segmentos tienen una mayor probabilidad de aparecer que otros.
Surgen problemas adicionales cuando se utiliza un generador de números pseudoaleatorios (PRNG). La generación de una secuencia pseudoaleatoria de dichos generadores está completamente determinada por su estado interno al comienzo de la generación. Un programa de reproducción aleatoria basado en dicho generador no puede crear más permutaciones que el número de estados internos del generador. Incluso cuando el número de posibles estados del generador se superpone al número de permutaciones, algunas permutaciones pueden ocurrir con más frecuencia que otras. Para evitar que se produzca una distribución desigual, el número de estados internos del generador de números aleatorios debe superar el número de permutaciones en varios órdenes de magnitud.
Por ejemplo, el generador de números pseudoaleatorios incorporado que se encuentra en muchos lenguajes de programación y bibliotecas generalmente usa un número de 32 bits para estados internos, lo que significa que dicho generador solo puede generar 232 números aleatorios diferentes. Si dicho generador se usara para barajar una baraja de 52 cartas , ¡podría generar una fracción muy pequeña de 52! ≈ 2225,6 permutaciones posibles. Un generador con menos de 226 bits de estados internos no puede generar todas las permutaciones de una baraja de 52 naipes. Se cree que para crear una distribución uniforme, se necesita un generador con estados de al menos 250 bits.
Naturalmente, ningún generador de números pseudoaleatorios puede crear más secuencias aleatorias dadas por diferentes datos iniciales que el número de estos datos iniciales. Entonces, un generador con estados internos de 1024 bits, para los cuales se dan parámetros iniciales de 32 bits, puede crear solo 232 secuencias de permutación diferentes. Puede obtener más permutaciones eligiendo suficientes números aleatorios del generador antes de usarlos en el algoritmo de reproducción aleatoria, pero este enfoque es muy ineficiente: muestrear, digamos, 2 30 números aleatorios antes de usar la secuencia en el algoritmo de reproducción aleatoria solo aumenta el número de permutaciones. a 2 62 .
Otro problema surge cuando se usa un PRNG congruente lineal simple , cuando el resto de la división se usa para reducir el intervalo de números aleatorios, como se mencionó anteriormente. El problema aquí es que los bits inferiores de un PRNG congruente lineal son menos aleatorios en comparación con los bits superiores; los n bits inferiores tienen un período de 2 n como máximo . Si el divisor es una potencia de dos, tomar el resto significa descartar los bits de orden superior, lo que da como resultado una reducción significativa de la aleatoriedad.
Finalmente, cabe señalar que incluso utilizando un generador fino, puede surgir una falla en el algoritmo debido al uso incorrecto del generador. Imagine, por ejemplo, que la implementación Java del algoritmo crea un nuevo generador para cada llamada al proceso de reproducción aleatoria sin establecer parámetros en el constructor. La hora actual (System.currentTimeMillis()) se utilizará para inicializar el generador. Por lo tanto, dos llamadas con una diferencia de tiempo de menos de un milisegundo darán permutaciones idénticas. Es casi seguro que esto sucederá si el barajado se produce repetida y rápidamente, lo que da como resultado una distribución muy desigual de las permutaciones. El mismo problema puede surgir al recibir números aleatorios de dos flujos diferentes. Es más correcto usar una instancia estática del generador, definida fuera de la rutina de reproducción aleatoria.