[104790] in Cypherpunks
Re: Shuffling
daemon@ATHENA.MIT.EDU (Jim Gillogly)
Wed Oct 28 20:10:47 1998
Date: Wed, 28 Oct 1998 16:13:37 -0800
From: Jim Gillogly <jim@acm.org>
To: coderpunks@toad.com
Reply-To: Jim Gillogly <jim@acm.org>
Anonymous asks:
> In the following snippet of pseudo-code, what should the value of
> SWAP_TIMES be to make the array A[] random, assuming ...
>
> for(i=0;i<SWAP_TIMES;i++){
> x=getrand();
> y=getrand();
> swap(A[x],A[y]);
> }
Indeterminate -- it could be a long time before you pick every number to
swap with something. Instead use Knuth's "Algorithm P" from Seminumerical
Algorithms (Vol. 2 of The Art of Computer Programming), which is linear
in the length of the table and uses only one random number per swap.
--
Jim Gillogly
8 Blotmath S.R. 1998, 00:10
12.19.5.11.10, 8 Oc 3 Zac, Fifth Lord of Night
