array - Longitud máxima de la lista para mezclar con Python random.shuffle?
shuffle array python (3)
Tengo una lista que mezclo con la función de mezcla integrada de Python ( random.shuffle )
Sin embargo, los estados de referencia de Python:
Tenga en cuenta que, incluso para
len(x)bastante pequeño, el número total de permutaciones de x es mayor 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 "len (x)" algo pequeño. 100, 1000, 10000, ...
Escribí ese comentario en la fuente de Python originalmente, así que tal vez pueda aclararlo ;-)
Cuando se introdujo el comentario, el generador Wichmann-Hill de Python tuvo un período mucho más corto, y no pudimos siquiera 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
Lo que quieren decir es que las permutaciones en n objetos (notado n!) Crece absurdamente alto muy rápido.
Básicamente n! = nx 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)
Entonces, básicamente, hay tantas permutaciones posibles que la confusión tomará de que probablemente no haya una razón real para preocuparse por las que no sucederá.
Pero si realmente es un problema (¿un cliente molesto que pide una garantía de aleatoriedad, quizás?), También podría descargar la tarea a un tercero; ver http://www.random.org/ por ejemplo.
TL; DR: Se "rompe" en listas con más de 2080 elementos, pero no te preocupes demasiado :)
Respuesta completa:
Antes que nada, observe que "barajar" una lista puede entenderse (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 e independientes 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 ".
Entonces, dado todo eso, si su lista es tal que hay 2**19937 o más permutaciones, algunas de ellas nunca se obtendrán al barajar 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.
Entonces, ves, no es exactamente una cuestión de cuánto tiempo es tu lista (aunque eso sí 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 arrojarían 2081! permutaciones, que es más de 2**19937 .