1: // sample -- Make a random permutation of the contents of an array.

  3: #include <stdio.h>

  5: #include "permuted_sample.H"
  6: #include "prng.H"


  9: // Nijenhuis & Wiff's random permutation algorithm RANPER, "Combinatorial Algorithms" pp 62-64.
 10: //
 11: void permute(prng rand, long* slot, long n) {
 12:   long m;                                         // loop index
 13:   long R;                                         // a random number
 14:   long t;                                         // temp for swapping 2 slots

 16:   for (m = 0; m < n; m++) {                       // for all slots in the array

 18:     R = rand.next(m, n);                          // pick a slot ahead of the current one

 20:     t = slot[m];                                  // swap that slot with the current one
 21:     slot[m] = slot[R];
 22:     slot[R] = t;
 23:   }
 24: }


 27: permuted_sample::permuted_sample(prng rand, long n, long N) {
 28:   slot = new long[n];                             // make an array to hold the samples
 29:   sample(rand, slot, n, N);                       // take a random sample
 30:   permute(rand, slot, n);                         // permute its ordering
 31: }


 34: permuted_sample::~permuted_sample() {             // destroy a sample
 35:   delete[] slot;
 36: }


 39: long permuted_sample::operator()(long i) {        // fetch sample[i]
 40:   return slot[i];
 41: }