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 <clive@pisquaredoversix.force9.co.uk> 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)