Puzzle DE46

Randomly scramble the elements in an array

[H-7] Write function randomly mixes up the elements of an integer array. Here is a sample run:

Original Array:
     0      1      2      3      4      5      6      7      8      9
    10     11     12     13     14     15     16     17     18     19
    20     21     22     23     24     25     26     27     28     29
    30     31     32     33     34     35     36     37     38     39
    40     41     42     43     44     45     46     47     48     49

Scrambled Array:
    17     10     24     20     26     49      9     41     44     47
    34     37     21     16      7     29      1      3     32     25
    35     38      2     13     40     33      8     23     30     45
    18     12     28      0     46     31     27      6     19     14
    48     11      5     39     43     15     22     42     36      4

In the example, the array starts with its elements in order, but it could start with any ordering of its elements. After being scrambled, any element might end up in any slot with equal probability. Since a slot might get any value with equal probability, the average of the values it gets over a large number of trials should be the average of all the numbers in the array.

Here is a testing framework:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int randInt( int min, int max );

/* Puzzle D46 -- randomly scramble the elements in an array */

/* Randomly assign each element a location in the array */
void scrambleArray( int size, int arr[] )
{
   . . . .
}

/* Generate a random integer  min <= r <= max */
int randInt( int min, int max )
{
  return (rand()*(max-min+1))/(RAND_MAX+1) + min ;
}

void fillArrayInOrder( int size, int arr[] )
{
  int j;
  
  for ( j=0; j<size; j++ )
  {
    arr[j] = j;
  }
}

void printArray( int size, int arr[] )
{
  const int N = 10;
  int j;
  
  for ( j=0; j<size; j++ )
  {
    if ( j%N == N-1 )
      printf("%6d\n", arr[j] );
    else
      printf("%6d ", arr[j] );
  }
}

int main()
{
  const int SIZE = 100;
  const int TRIALS = 1000;    /* Number of times to repeat the experiment */
  int x[ SIZE ];              /* The array to be scrambled */
  double sum[ SIZE ];         /* Sum of the elements that end up in each cell */
                              /* after TRIALS scramblings */
  int i, j, k ;
  
  srand( time(NULL) );
  
  /* Demonstrate the scrambling */
  printf("\nOriginal Array:\n");
  fillArrayInOrder( SIZE, x );
  printArray( SIZE, x );
  printf("\n\n");
  
  scrambleArray( SIZE, x );
  printf("\nScrambled Array:\n");
  printArray( SIZE, x );
  
  for ( i=0; i<SIZE; i++ ) sum[i] = 0.0;
  
  /* Initialize and scramble the array TRIALS times */
  for ( j=0; j<TRIALS; j++ )
  {
    fillArrayInOrder( SIZE, x );
    scrambleArray( SIZE, x );
    
    /* add up values that end up in each cell */
    for ( i=0; i<SIZE; i++ )
      sum[i] += x[i] ;
  }
  
  printf("\n\nAverage value for each location. ");
  printf("(Each should be about %6.4lf):\n\n", (double)(SIZE-1)/2.0 );

  for ( k=0; k<SIZE; k++ )
  {
    printf("%6.4lf, ", sum[k]/TRIALS  );
    if ( k%10 == 9 ) printf("\n" );
  }
  printf("\n");
  return 0;
}