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)