From: eclrh@sun.leeds.ac.uk (Robert Hill)
Subject: Re: Shuffling
Date: Wed, 10 Feb 1999 17:58:45 +0000 (GMT)
Newsgroups: sci.math
Keywords: Fairest algorithm to generate random permutation
In article <36BF02F3.86EE5A04@pisquaredoversix.force9.co.uk>, Clive Tooth writes:
> Today's mildly interesting randomization fact:
>
> The normal algorithm (call it A1) for shuffling N items is something
> like:
>
> for i:= N downto 1 do begin
> j:= Random(1, i)
> InterchangeItems(i, j)
> end
>
> An algorithm (call it A2) which may seem as good, if not better, is:
>
> for i:= N downto 1 do begin
> j:= Random(1, N)
> InterchangeItems(i, j)
> end
>
> However, if N>2, A1 is always a fairer shuffler than A2.
Even Knuth was unreliable at first over random shuffling. In the first
edition of vol 2 he recommends your A1 as the best method, but only after
also mentioning as acceptable a method based on simulation of some aspects
of human shuffling of cards.
In the second edition, your A1 is the only method he considers worthy of
describing. He says: "A moment's reflection is enough to convince
oneself that the approaches people traditionally use to shuffle cards are
miserably inadequate; there is no hope of obtaining each of the t!
permutations with anywhere near equal probability by such methods."
--
Robert Hill
University Computing Service, Leeds University, England
"Though all my wares be trash, the heart is true."
- John Dowland, Fine Knacks for Ladies (1600)