[Tutor] Deal a Random Deck - Challenge

[Zak Arntson]

> 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]
###

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