Python's random.shuffle limitation

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.

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.