Longitud máxima de la lista para mezclar con Python random.shuffle?

Question

tengo una lista que barajo con el pitón construido en función de reproducción aleatoria (random.shuffle)

Sin embargo, los estados de referencia de Python:

Tenga en cuenta que incluso bastante pequeño len(x), el número total de permutaciones de x es más grande que el período de la mayoría de los generadores de números aleatorios; esto implica que la mayoría de las permutaciones de una secuencia larga nunca se pueden generar.

Ahora, me pregunto qué significa "bastante pequeño len (x)". 100, 1000, 10000, ...

Answer 1

TL; DR: "rompe" en las listas con más de 2.080 elementos, pero no se preocupe demasiado :)

La respuesta completa:

En primer lugar, observe que "aleatorio", una lista se puede entender (conceptualmente) como generar todas las permutaciones posibles de los elementos de las listas, y elegir una de estas permutaciones al azar.

Luego, debe recordar que todos los generadores de números aleatorios computarizados autónomos son en realidad "pseudo" aleatorios. Es decir, en realidad no son aleatorios, sino que se basan en una serie de factores para tratar de generar un número difícil de adivinar en avanzado o reproducido a propósito. Entre estos factores suele ser el número generado anteriormente. Entonces, en la práctica, si usa un generador aleatorio de manera continua un cierto número de veces, eventualmente comenzará a obtener la misma secuencia de nuevo (este es el "período" al que se refiere la documentación).

Finalmente, el docstring en Lib/random.py (el módulo aleatorio) dice que "El período [del generador de números aleatorios] es 2**19937-1."

Por lo tanto, dado todo eso, si su lista es tal que hay 2**19937 o más permutaciones, algunas de ellas nunca se obtendrán al mezclar la lista. Generaría (nuevamente, conceptualmente) todas las permutaciones de la lista, luego generaría un número aleatorio x y elegiría la permuta xth. La próxima vez, genere otro número aleatorio y, y elija la permutación yth. Y así. Pero, dado que hay más permutaciones que números aleatorios (porque, como máximo después de 2**19937-1 números generados, volverás a obtener los mismos), comenzarás a elegir las mismas permutaciones nuevamente.

Así que, ves, no es exactamente una cuestión de cuánto tiempo es tu lista (aunque eso sí que entra en la ecuación). Además, 2**19937-1 es un número bastante largo. Pero, aún así, dependiendo de tus necesidades de barajado, deberías tener eso en cuenta. En un caso simplista (y con un cálculo rápido), para una lista sin elementos repetidos, 2081 elementos producirían 2081! permutaciones, que es más que 2**19937.

Answer 2

Lo que quieren decir es que las permutaciones en n objetos (notado n!) Crece absurdamente alto muy rápido.

Básicamente n! = n x n-1 x ... x 1; por ejemplo, 5! = 5 x 4 x 3 x 2 x 1 = 120 lo que significa que hay 120 maneras posibles de barajar una lista de 5 elementos.

En la misma documentación de la página de Python dan 2^19937-1 como el período, que es 4. algo × 10^6001 o algo así. Basado en la página de Wikipedia sobre factoriales, ¡supongo 2000! debería estar alrededor de eso. (Lo siento, no encontré la cifra exacta.)

Así que, básicamente, hay tantas permutaciones posibles que la confusión llevará a que probablemente no haya una razón real para preocuparse por las que no.

Pero si realmente es un problema (¿un cliente molesto pidiendo una garantía de aleatoriedad quizás?), También podría descargar la tarea a un tercero; ver http://www.random.org/ por ejemplo.

Answer 3

que escribió ese comentario en el código fuente de Python en un principio, por lo que tal vez pueda aclarar ;-)

Cuando se introdujo el comentario, generador Wichmann-Hill de Python tuvo un período mucho más corto, y ni siquiera podría generar todas las permutaciones de una baraja de cartas.

El período es astronómicamente más grande ahora, y 2080 es correcto para el límite superior actual. Los documentos podrían reforzarse para decir más sobre eso, pero serían terriblemente tediosos.

Hay una explicación muy simple: un PRNG de período P tiene P posibles estados de inicio. El estado inicial determina por completo la permutación producida. Por lo tanto, un PRNG del período P no puede generar más de P permutaciones distintas (y eso es un límite superior absoluto, es posible que no se logre). Es por eso que comparar N! a P es el cálculo correcto aquí. Y, de hecho:

>>> math.factorial(2080) > 2**19937 - 1 
False 
>>> math.factorial(2081) > 2**19937 - 1 
True