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