🚀 go-pugleaf

In article <1992Aug22.190826.13877@raven.alaska.edu> ejo@kaja.gi.alaska.edu (Eric J. Olson) writes:
...
> Thanks to all the people who answered; there were some good solutions,
> and the most common (and simplest) one runs as follows; if you have a
> list of N elements (integers here for demonstration) and random(x)
> produces a random number between 0 and (x-1) inclusive:
> 
> mix(deck)
> int deck[N];
> {
> int i,j,temp;
> 
> for (i=0;i<N;i++)
>   {
>     j=random(N);
>     temp=deck[i];
>     deck[i]=deck[j];
>     deck[j]=temp;
>   }
> }

There's only one problem with this solution:  it will not
produce a random distribution.  In particular, low numbers are
more likely to end up near the beginning of the list.

Instead, try

	mix(deck)
	int deck[N];
	{
  	  int i,j,temp;

	  for( i = 1; i < N; i++ ) {
	    j = random( i + 1 );
	    temp = deck[i];
	    deck[i] = deck[j];
	    deck[j] = tmp;
	  }
	}

This provably randomizes the list, by induction:

	Base Case:

	  deck[0] is a "disordered" list of the numbers from 0
	  to 0 inclusive.

	Inductive Case:
	  
	  Assume that deck[0]..deck[k-1] contains a disordered
	  list of the numbers from 0..k-1 inclusive.  Now we
	  exchange deck[k] either with itself with probability
	  1/(k+1) or with some element of our disordered list
	  with probability k/(k+1) .  This means that there is
	  an equal likelihood that deck[k] will appear in any
	  position, and since the element being swapped was
	  chosen equiprobably from elements deck[0]..deck[k],
	  there is an equal probability of any element
	  appearing in deck[k].  The remaining elements are by
	  induction already disordered, so we now have a
	  disordered list of the numbers 0..k inclusive in
	  deck[0]..deck[k].

Exercise (simple): 
	
	Modify this algorithm so that instead of disordering a
	previously built list, it simply builds a list in
	disorder directly (solution below).

					Bart Massey
					bart@cs.uoregon.edu

Here's a C program to demonstrate the problem.  Compile it with
and without -DBAD and look at the results.  This is how I checked
my work.

-----

#define N 20

extern long random( void );
extern int atoi( char * );
extern void printf( const char *, ... );

int main(int argc, char **argv) {
  int trials = atoi(argv[1]);
  int deck[N];
  double score[N];
  int i, j;

  for( i = 0; i < N; i++ )
    score[i] = 0;

  for( i = 0; i < trials; i++ ) {
#ifdef BAD  
    /* set up deck */
    for( j = 0; j < N; j++ )
      deck[j] = j;
    /* do shuffle */
    for( j = 0; j < N; j++ ) {
      int k = (random() >> 3) % N;
      int tmp;

      tmp = deck[ j ];
      deck[ j ] = deck[ k ];
      deck[ k ] = tmp;
    }
#endif
#ifndef BAD
    /* do shuffle */
    deck[0] = 0;
    for( j = 1; j < N; j++ ) {
      int k = (random() >> 3) % ( j + 1 );

      deck[ j ] = deck[ k ];
      deck[ k ] = j;
    }
#endif
    /* score result based on first element */
    score[ deck[ 0 ] ] += (1.0 / (double) trials);
  }
    
  for( i = 0; i < N; i++ )
    printf( "%d: %g\n", i, score[i] );

  return 0;
}