card dealer

[Steven D'Aprano]

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