/*
 * This program is an example of how to shuffle an array.
 *
 * It is provided for illustrative purposes, 
 * It is placed in the public domain, thus has no copyright.
 *
 * Comments and bug reports about this program should be sent 
 * via email to scott@helsbreth.org
 *
 */


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

#define ulong unsigned long

/* ----------------------------------------------------------------------

COMBO

  a simple but very good combination generator.
  It combines, by addition mod 2^32,
            x(n)=x(n-1)*x(n-2) mod 2^32
        and
            y(n)=30903*y(n-1) + carry mod 2^16
 The period of the first is 3*2^29, on odd integers, and the
 period of the second, a multiply-with-carry generator, is
 30903*2^15-1=1012629503, so the period of combo exceeds 2^60.
 This generator is simple to program in Fortran or C and quite
 fast.

*/

/*
 Simple combo, period > 2^60.5
 x(n)=x(n-1)*x(n-2) mod 2^32 added to
 period of x(n)=x(n-1)*x(n-2) is 3*2^29 if both seeds are
    odd, and one is +or-3 mod 8.
 easy to ensure: replace seed x with 8*seed+3, and y with 2*seed+1
*/

static ulong combo_x = 3;
static ulong combo_y = 1;
static ulong combo_z = 1;
static ulong combo_v = 0;

void seed_rand_combo(ulong seed) {
    combo_x = seed * 8 + 3;
    combo_y = seed * 2 + 1;
    combo_z = seed | 1;
    combo_v = 0;
}

ulong rand_combo(void) {
    combo_v = combo_x * combo_y;
    combo_x = combo_y;
    combo_y = combo_v;
    combo_z = (combo_z & 65535) * 30903 + (combo_z >> 16);
    return combo_y + combo_z;
}

#define RAND_MAX_COMBO ((unsigned long) 4294967295)

/* ----------------------------------------------------------------------
  range
  
  returns a number between 0 and N-1
  without any bias.

*/

int range(int n) {
   unsigned long div;
   int r;

   div = RAND_MAX_COMBO/n;

   do {
      r = rand_combo() / div;
   } while (r >= n);

   return r;
}
/* -------------------------------------------------------------- */

/* ----------------------------------------------------------------------
   range2

   returns an integer between low and high inclusive

*/


int range2(int low, int high) {
   return low + range(high-low+1);
}

/* -------------------------------------------------------------- */


#define NUMBER_OF_ELEMENTS 20

int main() {
   int i, s, t;
   int array[NUMBER_OF_ELEMENTS];

   /* initialize the array */
   for (i=0; i<NUMBER_OF_ELEMENTS; i++) {
      array[i] = i;
   }

   /*
      'Randomize' the random number generator so it won't 
      produce the same sequence each time.
   */

   seed_rand_combo( (ulong) time(NULL) );

   /*
      Now 'shuffle' the array.
      The method is; pick a random element in the array
      and swap it with the first element.  Then pick a random
      element from the rest of the array and swap with the second
      and so on.
   */

   for (i=0; i<NUMBER_OF_ELEMENTS; i++) {
      /* Pick a random element */
      s = range2(i, NUMBER_OF_ELEMENTS-1);
   
      /* swap them */
      t = array[i];
      array[i] = array[s];
      array[s] = t;
   }

   for (i=0; i<NUMBER_OF_ELEMENTS; i++) {
      printf("%d ", array[i]);
   }
   printf("\n");

   return 0;
}