card dealer

[Antoon Pardon]

Op 28-09-13 12:31, Ned Batchelder schreef:
> On 9/28/13 2:01 AM, Steven D'Aprano wrote:
>> 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.
>>
>>
>
> I've thought that way about it too: there are so many shuffles any way,
> it won't be a problem.  But think about it like this:  if you shuffle a
> deck of 52 cards with a default Python random object, then once you have
> dealt out only 28 cards, the entire rest of the deck is completely
> determined.  That is, given the sequence of the first 28 cards, there's
> only one choice for how the remaining 24 will be dealt.  Depending on
> what you need from your deck of cards, that could be a complete disaster.

I don't see it. Unless given those 28 cards you can actually predict
those 24 other cards or at least can devise some betting strategy that
will allow you to beat the odds I don't see how this could lead to a
disaster.

> Is it a problem for a card game simulation?  No.  Is it a problem for a
> program that analyze correlations between the start of the deck and the
> end of the deck?  Maybe.

Well if a program would actually find a correlation between the start of
the deck and the end, that may indeed be a cause for worry. But what
evidence is there for that possibility?

-- 
Antoon Pardon