Xref: utzoo sci.math:17380 comp.lang.c:39254
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!psuvax1!rutgers!cbmvax!snark!eric
From: eric@snark.thyrsus.com (Eric S. Raymond)
Newsgroups: sci.math,comp.lang.c
Subject: Shuffle generation
Message-ID: <1bQCYz#6lHOhh7Jxk2b4WjLh65vrXpL=eric@snark.thyrsus.com>
Date: 13 May 91 15:12:52 GMT
Followup-To: poster
Lines: 38

In one of my programs, I have a requirement to generate random shuffles
of arbitrary size.  I am using the obvious method, as follows:

----------------------------- CUT HERE ------------------------------------
#define TRANSPOSITIONS(n)	(10 * n)

void shuffle(size, shuffle)
int size, *shuffle;
{
    int	i, j;

    for (i = 0; i < size; i++)
	shuffle[i] = i;
    for (i = 0; i < TRANSPOSITIONS(size); i++)
    {
	int	holder, k;

	j = roll(size);
	k = roll(size);

	holder = shuffle[k];
	shuffle[k] = shuffle[j];
	shuffle[j] = holder;
    }
}
----------------------------- CUT HERE ------------------------------------

Two questions:

1) Is there a known way of choosing a formula for TRANSPOSITIONS(n) to
   guarantee random mixing in some a priori sense?

2) This is, obviously, a naive method.  Is there a `smart' algorithm that
   works better?

Replies by email, please.
-- 
      Eric S. Raymond = eric@snark.thyrsus.com  (mad mastermind of TMN-Netnews)