Xref: utzoo sci.math:17429 comp.lang.c:39308
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!samsung!uunet!proto!joe
From: joe@proto.com (Joe Huffman)
Newsgroups: sci.math,comp.lang.c
Subject: Re: Shuffle generation
Message-ID: <1991May15.183447.1437@proto.com>
Date: 15 May 91 18:34:47 GMT
References: <1bQCYz#6lHOhh7Jxk2b4WjLh65vrXpL=eric@snark.thyrsus.com> <8c=sAju00Vp_Ihxl4r@andrew.cmu.edu>
Organization: Prototronics @ Sandpoint, Idaho
Lines: 39

dd2i+@andrew.cmu.edu (Douglas Michael DeCarlo) writes:

>In article <1bQCYz#6lHOhh7Jxk2b4WjLh65vrXpL=eric@snark.thyrsus.com>
>eric@snark.thyrsus.com (Eric S. Raymond) writes:
>> In one of my programs, I have a requirement to generate random shuffles
>> of arbitrary size.  I am using the obvious method, as follows:

>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 have a tournament scheduleing program that needs to do the 'draw' and
place some of the entries ('seeds' go in specific locations) in random
positions.  I used a similar algorithm at first (swap(random(N),random(N))
and discovered that it wasn't random enough.  I did the statisitical 
analysis but can't seem to find it right now.  The problem with mine was 
that there was an abnormally high probability that the i'th element would 
remain in it's original position.  I believe the above will suffer from the 
last few elements being unlikely to be moved to the beginning of the array.

Perhaps in DeCarlo's algorithm one could use 'swap(i, random(N))' instead
(I didn't think of that and haven't done the analysis).

What I ended up doing was something like this (which may not be feasible
in Raymond's case):

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--;
	}
}
-- 
joe@proto.com