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