From msuinfo!caen!uunet!cs.utexas.edu!milano!cactus.org!ritter Fri Jan 22 16:41:30 1993
Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles
Path: msuinfo!caen!uunet!cs.utexas.edu!milano!cactus.org!ritter
From: ritter@cactus.org (Terry Ritter)
Subject: Re: Looking for random permutation generation algorithms
Message-ID: <1993Jan16.032122.12732@cactus.org>
Followup-To: sci.crypt
Organization: Capital Area Central Texas UNIX Society, Austin, Tx
References: <1993Jan6.014749.15323@ee.ubc.ca> <sumner.727036572@milo.math.scarolina.edu>
Date: Sat, 16 Jan 1993 03:21:22 GMT
Lines: 84
Xref: msuinfo comp.theory:6239 sci.crypt:12975 sci.math:38373 rec.puzzles:20361


In <sumner.727036572@milo.math.scarolina.edu>
sumner@math.scarolina.edu (David Sumner) writes:

>To quickly generate a 'random' permutation of 1, 2, ..., n:
>
> ++++++++++++++
> Initialize A[n] as the array [1, 2, 3, 4,..., n]
>
> for i=1 to n
> z = random(n)
> t = a[i]
> a[i] = a[z]
> a[z] = t
> next i
> ++++++++++++++
>
>The loop exits with A holding a pseudo random permutation of
>1, 2, 3, ..., n.
>
>Assuming that random is a function that returns a random
>integer between 1 and n.

Alas, no. In general, the problem is in using "random(n)" instead
of "random(i)." Using "random(n)" gives us N * N * ... * N = N^N
possibilities, but there are only N! different permutations. Does
this make a difference?

Yes, indeed! This is, in fact, precisely the shuffling function
analyzed by Castellan [1]. In a correct shuffling algorithm, there
should be an equal probability that any particular element will end
up in any other position. But in this algorithm, Castellan shows
that, for a 10-element array, the probabilities vary almost two to
one, in a very systematic manner. This is a serious fault.

Compare the above function with the correct version (originally
published by Durstenfeld (1964) [2]) as described in Knuth II
[3:139]. Or, how about this (in Turbo Pascal, with Swap(x,y) as
one would expect):


VAR
x: ARRAY[ 0..N-1 ] OF ... { zero-based array of N elements }

VAR
i, j: WORD;

FOR i := N-1 DOWNTO 1 DO
BEGIN
j := Random( i + 1 ); { j = 0..i }
Swap( x[i], x[j] );
END;

For the first pass, select one of the N possible elements
{ x[0], x[1], ..., x[N-1] } and place the result in x[N-1].
(Move the element already in x[N-1] to replace the selected
element.) Thus, x[N-1] is any of N possible elements.

For the next pass, select one of the remaining N-1 elements
{ x[0], x[1], ..., x[N-2] } and place the result in x[N-2].
Thus, x[N-2] is any of N-1 possible elements.

For the last pass, we select one of the remaining two elements
{ x[0], x[1] } and place the result in x[1]; x[1] is one of
2 possible elements.

Total possibilities = N * N-1 * ... * 2 = N!, as expected.


References:

[1] Castellan, N. 1992. Shuffling arrays: Appearances may be
deceiving. Behavior Research Methods, Instruments, &
Computers. 24(1): 72-77.

[2] Durstenfeld, R. 1964. Algorithm 235, Random Permutation,
Procedure SHUFFLE. Communications of the ACM. 7: 420.

[3] Knuth, D. 1981. The Art of Computer Programming, Vol. 2,
Seminumerical Algorithms. 2nd Ed. Addison-Wesley.

---
Terry Ritter ritter@cactus.org