Tim Peters added the comment: When the comment was introduced, Python's Wichmann-Hill generator had a much shorter period, and we couldn't even generate all the permutations of a deck of cards.
The period is astronomically larger now, but the stackoverflow answer (2080) is correct for the current upper bound. The docs could be beefed up to say more about that - but they'd get awfully tedious ;-) To the OP, this is your error: it takes lg(N!) "bits of randomness" (lg is the logarithm to base 2) to generate _one_ random permutation. That says nothing about what's needed to generate _all_ permutations. With an RNG of period P, there are P possible starting states. The starting state wholly determines the permutation produced. Therefore an RNG of period P cannot generate more than P distinct permutations (and that's an absolute upper bound - it may not be achieved). That's why comparing N! to P is the correct computation here, and indeed: >>> math.factorial(2080) > 2**19937 - 1 False >>> math.factorial(2081) > 2**19937 - 1 True If you still don't believe it, here's a challenge: take a toy RNG with a small period, and use it to generate permutations (via any method you like). You'll find that you never get more distinct permutations than the period of your RNG. Then reread the above ;-) ---------- nosy: +tim.peters _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue18928> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
