Xref: utzoo sci.math:17448 comp.lang.c:39321
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!olivea!uunet!mcsun!hp4nl!charon!dik
From: dik@cwi.nl (Dik T. Winter)
Newsgroups: sci.math,comp.lang.c
Subject: Re: Shuffle generation
Message-ID: <3545@charon.cwi.nl>
Date: 16 May 91 12:12:53 GMT
References: <1bQCYz#6lHOhh7Jxk2b4WjLh65vrXpL=eric@snark.thyrsus.com> <8c=sAju00Vp_Ihxl4r@andrew.cmu.edu> <1991May15.183447.1437@proto.com>
Sender: news@cwi.nl
Followup-To: sci.math
Organization: CWI, Amsterdam
Lines: 25

In article <1991May15.183447.1437@proto.com> joe@proto.com (Joe Huffman) writes:
 > >To swap N items in an array A[0..(n-1)], the following O(N) algorithm works:
 > 
 > >for (i=0; i < N; i++) {
 > >     swap(i, i + random(N - i));
 > >}
 > 
 >             I used a similar algorithm at first (swap(random(N),random(N))
 > and discovered that it wasn't random enough.
This is not at all similar.
 > 
 > void shuffle(int n, list new_list, list org_list)
 > {
 > 	while(n)
 > 	{
 > 		element temp = get_and_remove_element(org_list,random(n));
 > 		add_element(new_list,temp);
 > 		n--;
 > 	}
 > }
And if you look long enough you will see that this is equivalent to the
originally proposed algorithm.
--
dik t. winter, cwi, amsterdam, nederland
dik@cwi.nl