Re: Random Permutation

Dave Seaman (ags@seaman.cc.purdue.edu)
Tue, 27 Feb 1996 15:56:54 +0100


In article <31288A79.41C67EA6@csi.uottawa.ca>,
Alioune Ngom <angom@csi.uottawa.ca> wrote:
>Hi everybody,
>
> Does anyone know of an algorithm that generate a random permutation
>of N?

The standard shuffling algorithm is described in Knuth,
_Seminumerical_Algorithms_ (Vol. 2 of "The Art of Computer Programming"),
p. 139 in the second edition. The algorithm amounts to the following:

for (i=0; i<N; i++)
a(i] = i;
for (j=N-1; j>0; j--) {
i = choose(0,j); /* Use your favorite random # gen. */
t = a[i];
a[i] = a[j];
a[j] = t;
}

where "i = choose(0,j)" is assumed to produce an integer value i, randomly
distributed over the interval 0 <= i <= j.

The most common mistake in designing shuffling algorithms is to use i =
choose(0,N-1), instead of choose(0,j). A little thought shows that
this cannot possibly generate a uniform distribution over all possible
permutations. There are N! different permutations to be generated, and
if each is to receive an equal probability, then the total number of
ways of assigning the random numbers in all trips through the loop
should be a number divisible by N!. However, the total number in this
case is n^(N-1) (or possibly N^N, if you make N trips through the
loop), and neither of these is evenly divisible by N! for N > 2.

Dave Seaman