Python's random.shuffle limitation
algorithm, python, random
Solution
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:
- Generate a list, `p`, of all possible permutations of the input
- Get a random number, `x`, from your PRNG
- The shuffled list is `p[x]`
If `p` is longer than the list of all possible `x`s 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.
Problem
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?