On Fri, 27 Sep 2013 17:40:46 -0400, Ned Batchelder wrote: > On 9/27/13 12:10 PM, Denis McMahon wrote: >> On Fri, 27 Sep 2013 12:08:33 +0000, Dave Angel wrote: >> >>> i recall >>> writing a shuffle function in C decades ago, which took an array of >>> (52) unique items and put them in random order. >> Whenever I tried to write shuffles I came up against a fairly >> fundamental limit: >> >> 52! > prng states >> >> Granted prngs seem to be better on the importing entropy from elsewhere >> front these days. >> >> > Python's PRNG holds plenty of state to handle card shuffling. Python's > random number generator has a period of 2**19337-1, so it has that many > states. That is much larger than 52!, about 10**5933 times larger. > (Unless I've botched the math...)
There's a warning about that in the docs: http://docs.python.org/3/library/random.html#random.shuffle [quote] 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. [end quote] If I've done that maths right, it turns out that 2025 is the largest number of items that a list can have for Python's default PRNG to generate every possible shuffle. But does it really matter? For most purposes, I'd say No. Even if you generated one trillion shuffles per second, you would have to keep shuffling for more than a trillion years before repeating yourself. To be pedantic: a *lot* more than a trillion years. Approximately 10**5789 trillion years. That's about a: trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion ... and so on for 57 more lines ... years. So in practice it's not really relevant that some shuffles won't be generated. They'll be randomly distributed throughout the space of all possible shuffles, which is so large that you really won't notice the missing ones. -- Steven -- https://mail.python.org/mailman/listinfo/python-list