limitación random.shuffle de Python

Question

Desde el Python documentation para random.shuffle, que toma una lista y cambia aleatoriamente el orden si sus elementos:

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

¿Es esto cierto en cualquier idioma, ya que la limitación parece depender del generador de números aleatorios? ¿Es posible escribir una función que pueda generar cualquier permutación posible de una lista arbitrariamente larga?

Answer 1

Ver http://mail.python.org/pipermail/python-ideas/2009-March/003670.html. La longitud exacta en la que comienza a ser un problema depende del PRNG, pero el problema básico siempre se aplicará.

La pregunta anterior a la que @TryPyPy se vincula también se centra en Python, pero la respuesta aceptada explica bastante bien por qué siempre sucederá. Parafraseando, se puede imaginar un algoritmo aleatorio ingenua trabajar de esta manera:

1. generar una lista, p, de todas las posibles permutaciones de la entrada
2. obtener un número aleatorio, x, desde su PRNG
3. El lista barajan es p[x]

Si p es más larga que la lista de todos los posibles x s que el PRNG puede producir, algunas de las permutaciones son inalcanzables.

Dado que los sofisticados algoritmos de mezcla son, en esencia, una forma de hacerlo sin tener que generar todas las permutaciones posibles antes de descartar todas menos una, la única forma de evitar esto es tener una fuente de aleatoriedad real.

Answer 2

Sí, es posible. Puede escribir un generador de permutación que use random.SystemRandom para todas sus decisiones.

La desventaja de esto es que su programa puede tener que detenerse por un tiempo arbitrariamente largo mientras su sistema operativo recolecta más entropía para su uso.