Shuffle generation
Joe Huffman
joe at proto.com
Thu May 16 04:34:47 AEST 1991
dd2i+ at andrew.cmu.edu (Douglas Michael DeCarlo) writes:
>In article <1bQCYz#6lHOhh7Jxk2b4WjLh65vrXpL=eric at snark.thyrsus.com>
>eric at 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 at proto.com
More information about the Comp.lang.c
mailing list