La reproducción aleatoria de Fisher-Yates es un algoritmo para generar una permutación aleatoria de una secuencia finita; en términos sencillos, el algoritmo mezcla la secuencia. El algoritmo pone efectivamente todos los elementos en un sombrero; determina continuamente el siguiente elemento dibujando aleatoriamente un elemento del sombrero hasta que no quedan elementos. El algoritmo produce una permutación insesgada : cada permutación es igualmente probable. La versión moderna del algoritmo es eficiente: lleva un tiempo proporcional al número de elementos que se barajan y los mezcla en su lugar .
El shuffle de Fisher-Yates lleva el nombre de Ronald Fisher y Frank Yates , quienes lo describieron por primera vez, y también se conoce como el shuffle de Knuth en honor a Donald Knuth . Se puede utilizar una variante de la combinación de Fisher-Yates, conocida como algoritmo de Sattolo , para generar permutaciones cíclicas aleatorias de longitud n en lugar de permutaciones aleatorias.
El método original de Fisher y Yates
El shuffle de Fisher-Yates, en su forma original, fue descrito en 1938 por Ronald Fisher y Frank Yates en su libro Tablas estadísticas para investigación biológica, agrícola y médica . [1] Su descripción del algoritmo utilizó lápiz y papel; una tabla de números aleatorios proporcionó la aleatoriedad. El método básico proporcionado para generar una permutación aleatoria de los números del 1 al N es el siguiente:
- Anote los números de 1 a N .
- Elija un número aleatorio k entre uno y el número de números sin tocar restantes (inclusive).
- Contando desde el extremo más bajo, tache el número k que aún no se haya tachado y escríbalo al final de una lista separada.
- Repita desde el paso 2 hasta que se hayan tachado todos los números.
- La secuencia de números escrita en el paso 3 es ahora una permutación aleatoria de los números originales.
Siempre que los números aleatorios seleccionados en el paso 2 anterior sean verdaderamente aleatorios e insesgados, también lo será la permutación resultante. Fisher y Yates se encargaron de describir cómo obtener tales números aleatorios en cualquier rango deseado de las tablas proporcionadas de una manera que evite cualquier sesgo. También sugirieron la posibilidad de usar un método más simple, elegir números aleatorios del uno a N y descartar cualquier duplicado, para generar la primera mitad de la permutación, y solo aplicar el algoritmo más complejo a la mitad restante, donde elegir un número duplicado sería de lo contrario, se vuelven frustrantemente comunes.
El algoritmo moderno
La versión moderna de Fisher-Yates shuffle, diseñada para uso de computadora, fue introducida por Richard Durstenfeld en 1964 [2] y popularizada por Donald E. Knuth en The Art of Computer Programming como "Algoritmo P (Shuffling)". [3] 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 se hayan percatado de ello. Las ediciones posteriores de The Art of Computer Programming de Knuth mencionan la contribución de Fisher y Yates. [4]
El algoritmo descrito por Durstenfeld difiere del dado por Fisher y Yates en una forma pequeña pero significativa. Mientras que una implementación informática ingenua del método de Fisher y Yates gastaría un tiempo innecesario 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 identificado en cada uno. iteración. Esto reduce la complejidad del tiempo del algoritmo a, en comparación con para la implementación ingenua. [5] Este cambio proporciona el siguiente algoritmo (para una matriz de base cero ).
- Para mezclar una matriz a de n elementos (índices 0 .. n -1): para i de n −1 hacia abajo a 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 de 0 a n −2 hacer j ← entero aleatorio tal que i ≤ j < n intercambie a [ i ] y a [ j ]
Ejemplos de
Método de lápiz y papel
Como ejemplo, permutaremos las letras de la A a la H usando el método original de Fisher y Yates . Comenzaremos escribiendo las letras en un papel borrador:
Distancia | Rodar | Rasga | Resultado |
---|---|---|---|
ABCDEFGH |
Ahora tiramos un número aleatorio k de 1 a 8-vamos a hacer que 3 y golpean a cabo el k ésimo (es decir, la tercera) letra en el bloc de notas y escriben en un papel como el resultado:
Distancia | Rodar | Rasga | Resultado |
---|---|---|---|
1-8 | 3 | AB | C |
Ahora seleccionamos un segundo número aleatorio, esta vez del 1 al 7: resulta ser 4. Ahora tachamos la cuarta letra que aún no se ha tachado del bloc de notas, que es la letra E, y la agregamos al resultado:
Distancia | Rodar | Rasga | Resultado |
---|---|---|---|
1-7 | 4 | AB | C E |
Ahora elegimos el siguiente número aleatorio del 1 al 6, y luego del 1 al 5, y así sucesivamente, siempre repitiendo el proceso de tachado como se indicó anteriormente:
Distancia | Rodar | Rasga | Resultado |
---|---|---|---|
1–6 | 5 | AB | CE G |
1–5 | 3 | AB | CEG D |
1-4 | 4 | AB | CEGD H |
1-3 | 1 | CEGDH A | |
1-2 | 2 | CEGDHA F | |
CEGDHAF B |
Método moderno
Ahora haremos lo mismo usando la versión del algoritmo de Durstenfeld: esta vez, en lugar de tachar las letras elegidas y copiarlas en otro lugar, las intercambiaremos con la última letra aún no elegida. Comenzaremos escribiendo las letras de la A a la H como antes:
Distancia | Rodar | Rasga | Resultado |
---|---|---|---|
ABCDEFGH |
Para nuestra primera tirada, sacamos un número aleatorio del 1 al 8: esta vez es 6, por lo que intercambiamos la sexta y octava letras de la lista:
Distancia | Rodar | Rasga | Resultado |
---|---|---|---|
1-8 | 6 | ABCDE H G | F |
El siguiente número aleatorio lo sacamos del 1 al 7, y resulta ser 2. Por lo tanto, intercambiamos la segunda y la séptima letras y seguimos adelante:
Distancia | Rodar | Rasga | Resultado |
---|---|---|---|
1-7 | 2 | A G CDEH | B F |
El siguiente número aleatorio que sacamos es del 1 al 6, y resulta que es 6, lo que significa que dejamos la sexta letra en la lista (que, después del intercambio anterior, ahora es la letra H) en su lugar y simplemente pasamos a la siguiente. paso. Nuevamente, procedemos de la misma manera hasta que se completa la permutación:
Distancia | Rodar | Rasga | Resultado | ||||
---|---|---|---|---|---|---|---|
1–6 | 6 | AGCDE | H BF | ||||
1–5 | 1 | E GCD | A HBF | ||||
1-4 | 3 | EG D | C AHBF | ||||
1-3 | 3 | P.EJ | D CAHBF | ||||
1-2 | 1 | GRAMO | E DCAHBF | ||||
En este punto no se puede hacer nada más, por lo que la permutación resultante es GEDCAHB F.
Variantes
El algoritmo "de adentro hacia afuera"
La reproducción aleatoria de Fisher-Yates, tal como la implementó Durstenfeld, es una reproducción aleatoria en el lugar . Es decir, dada una matriz preinicializada, baraja los elementos de la matriz en su lugar, en lugar de producir una copia barajada 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, se 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 anteriormente ocupaba esa posición a la posición i . En caso de que la posición aleatoria sea el número i , este "movimiento" (al mismo lugar) implica 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 en el que la fuente se define mediante una 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 modifica durante la ejecución.
Para inicializar una matriz a de n elementos en una copia aleatoria de la fuente , ambas basadas en 0: para i de 0 a n - 1, haga j ← entero aleatorio tal que 0 ≤ j ≤ i si j ≠ i a [ i ] ← a [ j ] a [ j ] ← fuente [ 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 uno de los n ! diferentes secuencias de números aleatorios que podrían obtenerse de las llamadas de random producirán una permutación diferente de los valores, por lo que todos estos se obtienen exactamente una vez. La condición que comprueba 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 costa de las asignaciones redundantes H n ≈ ln n + γ .
Otra ventaja de esta técnica es que n , el número de elementos en la fuente , no necesita conocerse de antemano; solo necesitamos poder detectar el final de los datos de origen cuando se alcanza. A continuación la matriz una está construida de forma iterativa a partir del vacío, y un .length representa el actual número de elementos vistos.
Para inicializar una matriz vacía una a una copia barajado al azar de fuente cuya longitud no se conoce: mientras fuente .moreDataAvailable j número entero ← aleatorio tal que 0 ≤ j ≤ un .length si j = un .length un .Append ( fuente .A continuación) else a .append ( a [ j ]) a [ j ] ← fuente .siguiente
Algoritmo de Sattolo
Cíclica permu- tación | Ejemplo |
---|---|
BCDA | ABCD → DABC → CDAB → BCDA → ABCD ... |
DABC | ABCD → BCDA → CDAB → DABC → ABCD ... |
BDAC | ABCD → CADB → DCBA → BDAC → ABCD ... |
CADB | ABCD → BDAC → DCBA → CADB → ABCD ... |
CDBA | ABCD → DCAB → BADC → CDBA → ABCD ... |
DCAB | ABCD → CDBA → BADC → DCAB → ABCD ... |
Las seis (3!) Permutaciones cíclicas de ABCD generadas por el algoritmo de Sattolo |
Sandra Sattolo publicó en 1986 un algoritmo muy similar para generar ciclos distribuidos uniformemente de longitud (máxima) n . [6] [7] La única diferencia entre los algoritmos de Durstenfeld y Sattolo es que en el último, en el paso 2 anterior, 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 para que la permutación resultante siempre consista 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 la reproducción aleatoria normal de Fisher-Yates. ¡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 del conjunto completo de todos los n ! posibles permutaciones.
El hecho de que el algoritmo de Sattolo siempre produzca un ciclo de longitud n se puede demostrar por inducción . Suponga 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 solo el algoritmo de Sattolo aplicado a esos primeros n - 1 elementos). Esto significa que rastreando el elemento inicial a su nueva posición p , luego el elemento originalmente en la posición p a su nueva posición, y así sucesivamente, uno solo regresa a la posición inicial después de haber visitado todas las demás posiciones. Suponga que la iteración inicial intercambia el elemento final con el que está en la posición (no final) k , y que la permutación subsiguiente de los primeros n - 1 elementos luego lo mueve 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. Rastreando posiciones sucesivas como se acaba de mencionar, no hay diferencia entre π y σ hasta llegar a la posición k . Pero luego, 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 para π sigue de nuevo la secuencia para σ , y todas las posiciones habrán sido visitadas antes de volver a la posición inicial, según sea necesario.
En cuanto a la probabilidad igual de las permutaciones, basta con observar que el algoritmo modificado implica ( n −1)! distintas secuencias posibles de números aleatorios producidas, 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 sea insesgada— con igual probabilidad. El ( n −1)! diferentes permutaciones así producidas agotan con precisión el conjunto de ciclos de longitud n : cada ciclo 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 del ciclo.
Una implementación de muestra del algoritmo de Sattolo en Python es:
de randrange de importación aleatoria def sattolo_cycle ( elementos ) -> Ninguno : "" "Algoritmo de Sattolo." "" i = len ( elementos ) while i > 1 : i = i - 1 j = randrange ( i ) # 0 <= j <= i-1 elementos [ j ], elementos [ i ] = elementos [ i ], elementos [ j ]
Comparación con otros algoritmos de barajado
La complejidad temporal y espacial asintótica de la mezcla de Fisher-Yates es óptima. Combinado con una fuente de números aleatorios no sesgados de alta calidad, también se garantiza que producirá resultados no sesgados. 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 la mitad, o incluso detener y reiniciar repetidamente, generando la permutación de forma incremental según sea necesario.
Método ingenuo
El método ingenuo de intercambiar cada elemento con otro elemento elegido al azar de todos los elementos está sesgado y fundamentalmente roto. [8] Diferentes permutaciones tendrán diferentes probabilidades de generarse, para cada, porque el número de permutaciones diferentes, , no divide uniformemente el número de resultados aleatorios del algoritmo, . En particular, según el postulado de Bertrand, habrá al menos un número primo entre y , y este número dividirá pero no dividir .
de randrange de importación aleatoria def naive_shuffle ( items ) -> None : "" "Un método ingenuo. Este es un ejemplo de lo que no se debe hacer - use Fisher-Yates en su lugar." "" n = len ( items ) for i in range ( n ): j = rango aleatorio ( n ) # 0 <= j <= n-1 elementos [ j ], elementos [ i ] = elementos [ i ], elementos [ j ]
Clasificación
Un método alternativo asigna un número aleatorio a cada elemento del conjunto que se va a mezclar y luego clasifica el conjunto de acuerdo con los números asignados. El método de clasificación tiene la misma complejidad temporal asintótica que Fisher-Yates: aunque la clasificación general es O ( n log n ), los números se clasifican de manera eficiente utilizando la clasificación Radix en tiempo O ( n ). Al igual que la reproducción aleatoria de Fisher-Yates, el método de clasificación produce resultados no sesgados. Sin embargo, se debe tener cuidado para garantizar que los números aleatorios asignados nunca se dupliquen, ya que los algoritmos de clasificación generalmente no ordenan los elementos al azar en caso de empate. [9] Además, este método requiere un espacio asintóticamente mayor: O ( n ) espacio de almacenamiento adicional para los números aleatorios, versus O (1) espacio para la mezcla de Fisher-Yates. Por último, observamos que el método de clasificación tiene una implementación paralela simple , a diferencia del shuffle de Fisher-Yates, que es secuencial.
Una variante del método anterior que se ha utilizado en los lenguajes que admiten la clasificación con funciones de comparación especificadas por el usuario es mezclar una lista clasificándola con una función de comparación que devuelve valores aleatorios. Sin embargo, este es un método extremadamente malo : es muy probable que produzca distribuciones altamente no uniformes, lo que además depende en gran medida del algoritmo de clasificación utilizado. [10] [11] Por ejemplo, suponga que la ordenación rápida se utiliza 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 posible posición final debe ser igualmente probable 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, que da posiciones cerca de la mitad de la secuencia con una probabilidad mucho mayor de que posiciones cerca de los extremos. Las funciones de comparación aleatorias aplicadas a otros métodos de clasificación como la clasificació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 la misma probabilidad (hasta que la elección se vea obligada por el agotamiento de una secuencia) no produce resultados con una distribución uniforme; en cambio, la probabilidad de elegir una secuencia debe 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 la misma 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 ejecución La ruta tendrá como probabilidad un número racional con como denominador una potencia de 2 , mientras que la probabilidad requerida será 1 / n ! porque cada posible permutación no es de esa forma [ cita requerida ] .
En principio, este método de mezcla puede incluso resultar en fallas del programa como bucles sin fin o violaciones de acceso, porque la corrección de un algoritmo de clasificación puede depender de las propiedades de la relación de orden (como la transitividad ) que una comparación que produce valores aleatorios ciertamente no tendrá. [12] Si bien este tipo de comportamiento no debería ocurrir con rutinas de clasificación que nunca realizan una comparación cuyo resultado se puede predecir con certeza (basado en 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 usarlo 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 clasificación.
Posibles fuentes de sesgo
Se debe tener cuidado al implementar el shuffle de Fisher-Yates, tanto en la implementación del algoritmo en sí como en la generación de los números aleatorios sobre los que se basa, de lo contrario los resultados pueden mostrar un sesgo detectable. A continuación se enumeran varias fuentes comunes de sesgo.
Errores de implementación
Un error común al implementar la combinación de Fisher-Yates es elegir los números aleatorios del rango incorrecto. El algoritmo defectuoso puede parecer que funciona correctamente, pero no producirá todas las posibles permutaciones con la misma probabilidad y es posible que no produzca ciertas permutaciones en absoluto. Por ejemplo, un error común de uno por uno sería elegir el índice j de la entrada a intercambiar en el ejemplo anterior para que sea siempre estrictamente menor que el índice i de la entrada con la que se intercambiará. Esto convierte el shuffle 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 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 que está sesgado, aunque de manera menos obvia. Esto se puede ver en el hecho de que al hacerlo se obtienen n n distintas secuencias posibles de intercambios, mientras que solo hay n ! posibles permutaciones de una matriz de n elementos. ¡Dado que n n nunca puede ser divisible uniformemente 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 mezclar una matriz de tres elementos [1, 2, 3]. Hay 6 posibles permutaciones de esta matriz (3! = 6), pero el algoritmo produce 27 posibles combinaciones (3 3 = 27). En este caso, [1, 2, 3], [3, 1, 2] y [3, 2, 1] resultan de 4 de las 27 combinaciones, mientras que cada una de las 3 permutaciones restantes se produce en 5 de las 27 baraja.
La matriz de la derecha muestra la probabilidad de que cada elemento en 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 mover una ranura hacia atrás tiene la probabilidad más alta.
Sesgo de módulo
Hacer una reproducción aleatoria de Fisher-Yates implica elegir 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. [13] Una forma simple y comúnmente utilizada de forzar tales números en un rango deseado es aplicar el operador de módulo ; 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 prácticamente garantiza que algunos de estos rangos no dividirán uniformemente el rango natural del generador de números aleatorios. Así, los remanentes no siempre estarán distribuidos uniformemente y, peor aún, el sesgo será sistemáticamente a favor de pequeños remanentes.
Por ejemplo, suponga que su fuente de números aleatorios da números del 0 al 99 (como fue el caso de las tablas originales de Fisher y Yates), y que desea obtener un número aleatorio imparcial del 0 al 15. Si simplemente divide los números por 16 y tome el resto, encontrará que los números del 0 al 3 ocurren aproximadamente un 17% más a menudo que otros. Esto se debe a que 16 no divide uniformemente 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 seguir intentándolo de nuevo hasta que aparezca un número en el rango adecuado. Si bien, en principio, esto podría, en el peor de los casos, demorar una eternidad, el número esperado de reintentos siempre será inferior a uno.
Un problema relacionado ocurre con las implementaciones que primero generan un número de punto flotante aleatorio , generalmente 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 de coma flotante aleatorios, por muy cuidadosamente generados, 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 un número 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á existiendo.
Generadores pseudoaleatorios
pedazos de semilla | longitud máxima de la lista |
---|---|
0 | 1 |
1 | 2 |
3 | 3 |
5 | 4 |
7 | 5 |
10 | 6 |
13 | 7 |
dieciséis | 8 |
22 | 10 |
24 | 10 |
32 | 12 |
48 | dieciséis |
64 | 20 |
128 | 34 |
160 | 40 |
226 | 52 |
256 | 57 |
512 | 98 |
1024 | 170 |
1600 | 245 |
19937 | 2080 |
44497 | 4199 |
Se produce un problema adicional cuando se usa el shuffle de Fisher-Yates con un generador de números pseudoaleatorios o PRNG: dado que la secuencia de números generada por dicho generador está completamente determinada por su estado interno al comienzo de una secuencia, un shuffle impulsado por tal El generador no puede producir permutaciones más distintas de las que el generador tiene distintos estados posibles. [14] Incluso cuando el número de estados posibles excede el número de permutaciones, la naturaleza irregular del mapeo 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 proporcionado por 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 de números diferentes. Si se usa un generador de este tipo para barajar una baraja de 52 cartas , ¡solo puede producir una fracción muy pequeña de las 52! ≈ 2225,6 posibles permutaciones. Es imposible que un generador con menos de 226 bits de estado interno produzca todas las posibles permutaciones de una baraja de 52 cartas.
Ningún generador de números pseudoaleatorios puede producir secuencias más distintas, comenzando desde el punto de inicialización, que los valores 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, solo puede producir 2 32 permutaciones diferentes justo después de la inicialización. Puede producir más permutaciones si uno ejercita el generador muchas veces antes de comenzar a usarlo para generar permutaciones, pero esta es una forma muy ineficiente de aumentar la aleatoriedad: suponiendo que uno pueda arreglar para usar el generador un número aleatorio de hasta mil millones , digamos 2 30 para simplificar, los tiempos entre la inicialización y la generación de permutaciones, entonces el número de posibles permutaciones sigue siendo solo 2 62 .
Un problema adicional ocurre cuando se usa un PRNG lineal congruente simple con el método de reducción de rango de dividir y tomar resto descrito anteriormente. El problema aquí es que los bits de orden bajo de un PRNG congruente lineal con módulo 2 e son menos aleatorios que los de orden superior: [4] los n bits bajos del generador tienen un período de 2 n como máximo . Cuando el divisor es una potencia de dos, tomar el resto significa esencialmente desechar los bits de orden superior, de modo que uno termine con un valor significativamente menos aleatorio. Se aplican reglas diferentes si el LCG tiene un módulo principal, pero estos 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.
Ver también
- RC4 , un cifrado de flujo basado en barajar una matriz
- Muestreo de yacimientos , en particular el algoritmo R, que es una especialización del proceso aleatorio de Fisher-Yates
Referencias
- ^ Fisher, Ronald A .; Yates, Frank (1948) [1938]. Cuadros estadísticos para la investigación biológica, agrícola y médica (3ª ed.). Londres: Oliver y Boyd. págs. 26-27. OCLC 14222135 . Nota: la sexta edición, ISBN 0-02-844720-4 , está disponible en la web , pero ofrece un algoritmo de barajado diferente de CR Rao .
- ^ Durstenfeld, R. (julio de 1964). "Algoritmo 235: permutación aleatoria". Comunicaciones de la ACM . 7 (7): 420. doi : 10.1145 / 364520.364540 .
- ^ Knuth, Donald E. (1969). Algoritmos seminuméricos . El arte de la programación informática. 2 . Reading, MA: Addison – Wesley. págs. 139–140. OCLC 85975465 .
- ^ a b Knuth (1998). Algoritmos seminuméricos . El arte de la programación informática. 2 (3ª ed.). Boston: Addison – Wesley. págs. 12-15, 145-146. ISBN 0-201-89684-2. OCLC 38207978 .
- ^ Black, Paul E. (19 de diciembre de 2005). "Fisher-Yates shuffle" . Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología . Consultado el 9 de agosto de 2007 .
- ^ Sattolo, Sandra (30 de mayo de 1986). "Un algoritmo para generar una permutación cíclica aleatoria". Cartas de procesamiento de información . 22 (6): 315-3017. doi : 10.1016 / 0020-0190 (86) 90073-6 .
- ^ Wilson, Mark C. (21 de junio de 2004). "Descripción general del algoritmo de Sattolo" (PDF) . En F. Chyzak (ed.). Informe de investigación INRIA . Seminario de algoritmos 2002-2004 . 5542 . resumen de Éric Fusy. págs. 105-108. ISSN 0249-6399 .
- ^ "El peligro de la ingenuidad" . Jeff Atwood . 2007-12-07 . Consultado el 7 de diciembre de 2019 .
- ^ "Algoritmos aleatorios demostrablemente perfectos" . Oleg Kiselyov . 3 de septiembre de 2001 . Consultado el 9 de julio de 2013 .
- ^ "Una simple mezcla que no resultó tan simple después de todo" . requieren 'cerebro' . 2007-06-19 . Consultado el 9 de agosto de 2007 .
- ^ "Haciendo el Microsoft Shuffle: falla del algoritmo en la boleta del navegador" . Rob Weir: una disposición antigua . 2010-02-27 . Consultado el 28 de febrero de 2010 .
- ^ "Escribiendo una función de comparación de clases, redux" . requieren 'cerebro' . 2009-05-08 . Consultado el 8 de mayo de 2009 .
- ^ La biblioteca GNU C: ISO aleatorio
- ^ Arndt, Jörg (2009). Generación de permutaciones aleatorias (tesis doctoral) (PDF) . Universidad Nacional de Australia. pag. 9 . Consultado el 25 de abril de 2018 .
enlaces externos
- Un ejemplo interactivo