Re: Shuffling

Jim Gillogly (jim@acm.org)
Wed, 28 Oct 1998 16:13:37 -0800

• Next message: Anonymous: "Re: Java applet security, exportability, Jon Postel haiku"
• Previous message: Anonymous: ""kid sister" resources underestimated?"
• In reply to: Mail System Internal Data: "DON'T DELETE THIS MESSAGE -- FOLDER INTERNAL DATA"
• Next in thread: Alex Alten: "Re: Shuffling"
• Reply: Alex Alten: "Re: Shuffling"

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

• Next message: Anonymous: "Re: Java applet security, exportability, Jon Postel haiku"
• Previous message: Anonymous: ""kid sister" resources underestimated?"
• In reply to: Mail System Internal Data: "DON'T DELETE THIS MESSAGE -- FOLDER INTERNAL DATA"
• Next in thread: Alex Alten: "Re: Shuffling"
• Reply: Alex Alten: "Re: Shuffling"