Home Original page

random.shuffle?

Tim Peters tim_one at email.msn.com
Mon Jul 31 15:13:22 EDT 2000 
[Erik Max Francis]
> ...
> Better would be this:
>
>     def shuffle(list):
>         count = len(list)
>         for i in range(count):
>             j = whrandom.randint(count)
>             list[i], list[j] = list[j], list[i]
>
> Simpler, too.

Actually, random.shuffle was added to Python to stop that bad algorithm from
propagating!  *That's* the biased one.  The easiest way to see that it must
be biased is that there are count**count possible outcomes (you pick one of
count values for j on each of count iterations), and count! does not divide
count**count for count > 2:  some permutations are thus necessarily more
likely than others, provided the list has at least 3 elements.

Note that there are count! possible outcomes in François's paraphrase of the
std Python random.shuffle.  That doesn't mean it's unbiased, but does mean
that it's at worst not so *obviously* biased <wink>.

Exhaustive discussion can be found via DejaNews.
More information about the Python-list mailing list