[Tutor] Deal a Random Deck - Good news

[Gregor Lingl]

Zak Arntson schrieb:

>>Zak Arntson wrote:
>>    
>>
>>>Here's an interesting problem a coworker (former mentor) uses when
>>>hiring:
>>> * Write an algorithm to deal out a set of "cards"
>>>      
>>>
>>Straightforward to do poorly. :-)  I think all of the solutuions you
>>posted are biased.  See:
>>    http://groups.google.com/groups?selm=LNBBLJKPBEHFEDALKOLCKEDFGNAA.tim_one%40email.msn.com
>>
>>Cheers,
>>  Neil
>>    
>>
>
>Actually, that algorithm is subtly different. It looks like:
>###
>import random
>def shuffle_biased(list):
>    count = len(list)
>    for i in range(count):
>        j = random.randint(count)
>        list[i], list[j] = list[j], list[i]
>###
>
>Where the proper (i.e., non-biased) solution using element swapping looks
>like:
>###
>import random
>def shuffle_unbiased(list):
>    count = len(list)
>    for i in range(count):
>        j = random.randrange(i, count)
>        list[i], list[j] = list[j], list[i]
>###
>  
>

Actually shuflle from module random is defined similarly, but using 
random.random(),
i.e. generating random reals, as this is approximately twice as fast as 
creating random
integers. (I think this is the reason, why deck3 is so much faster than 
deck1 or deck2,
but slower than deck4 or deck5 - because they don't need to sort.

Here the code for shuffle from module random:

    def shuffle(self, x, random=None, int=int):
        """x, random=random.random -> shuffle list x in place; return None.

        Optional arg random is a 0-argument function returning a random
        float in [0.0, 1.0); by default, the standard random.random.

        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.
        """

        if random is None:
            random = self.random
        for i in xrange(len(x)-1, 0, -1):
            # pick an element in x[:i+1] with which to exchange x[i]
            j = int(random() * (i+1))
            x[i], x[j] = x[j], x[i]

Wow! The docstring explains, that there is another reason for shuffle
to be biased, which is independent of shuffle's algorithm but depends
solely on the random generator used.

Up to Python 2.2 a Wichmann-Hill generator with period
6,953,607,871,644 was used. This is smaller than 16! = 20922789888000.
This means, that Python2.2's shuffle cannot generate all permutations of
sequences with more than 15 Elements.And already for 16 Elements only a 
third of all
possible permutations is generated.

This was changed with Python 2.3 using a Mersenne Twister generator
with period 2**19937-1 (which is an integer with 6002 digits).
Since 2080! < 2**19937-1 < 2081!, Python 2.3's shuffle should be fairly
unbiased for sequences with length nearly up to 2080.

And the other good news:

Python 2.3's random generator is more than 20% faster than the old one.

Regards,
Gregor
   

>The difference is in choosing j. In the shuffle_biased the value at j can
>be swapped a ton of times. In the shuffle_unbiased, when the value at j is
>swapped, it cannot be swapped again.
>
>---
>Zak Arntson
>www.harlekin-maus.com - Games - Lots of 'em
>
>
>
>_______________________________________________
>Tutor maillist  -  Tutor@python.org
>http://mail.python.org/mailman/listinfo/tutor
>
>
>  
>