Python's random.shuffle limitation

Question

From the Python documentation for random.shuffle, which takes a list and randomizes the order if its elements:

Note that for even rather small len(x), the total number of permutations of x is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated.

Is this true of any language, since the limitation seems dependent on the random number generator? Is it possible to write a function that can generate any possible permutation of an arbitrarily long list?

Answer 1

See http://mail.python.org/pipermail/python-ideas/2009-March/003670.html . The exact length that it starts being a problem at is dependent on the PRNG, but the basic problem will always apply.

The previous question that @TryPyPy linked to is also focused on Python, but the accepted answer explains quite well why it will always happen. To paraphrase, you can imagine a naive shuffle algorithm working this way:

1. Generate a list, p, of all possible permutations of the input
2. Get a random number, x, from your PRNG
3. The shuffled list is p[x]

If p is longer than the list of all possible xs that the PRNG can produce, some of the permutations are unreachable.

Since fancy shuffle algorithms are, at their core, a way of doing this without having to generate every possible permutation before discarding all but one of them, the only way around this is to have a source of true randomness.

Answer 2

Yes, it is possible. You can write a permutation generator that uses random.SystemRandom for all of your decisions.

The downside of this is that your program may have to halt for an arbitrarily long time while your operating system collects more entropy for you to use.