This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author tim.peters
Recipients dbenbenn, docs@python, r.david.murray, rhettinger, tim.peters
Date 2013-09-05.04:20:33
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <>
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
>>> math.factorial(2081) > 2**19937 - 1

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 ;-)
Date User Action Args
2013-09-05 04:20:34tim.peterssetrecipients: + tim.peters, rhettinger, dbenbenn, r.david.murray, docs@python
2013-09-05 04:20:34tim.peterssetmessageid: <>
2013-09-05 04:20:34tim.peterslinkissue18928 messages
2013-09-05 04:20:33tim.peterscreate