1: // random_sample -- Make a random sample of a set n integers from the interval [0..N)

  3: #include <stdio.h>

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


  9: // Knuth's random sample algotithm S, "Seminumerical Algorithms" pp 121-123.
 10: //
 11: void sample(prng rand, long* slot, long n, long N) { // take a random sample
 12:   long t;                                       // counts up to N
 13:   long m = 0;                                   // counts up to n

 15:   for (t = 0; m < n; t++) {                     // loop till all n slots are chosen
 16:     if (rand.next(0, N - t) < n - m) {          // do we select this from 0..N?
 17:       slot[m++] = t;                            // yes,
 18:     }
 19:   }
 20: }


 23: random_sample::random_sample(prng rand, long n, long N) { // construct a random sample
 24:   slot = new long[n];                           // make an array to hold the samples
 25:   sample(rand, slot, n, N);                     // take a sample
 26: }


 29: random_sample::~random_sample() {               // destroy a sample
 30:   delete[] slot;
 31: }


 34: long random_sample::operator()(long i) {        // fetch sample[i]
 35:   return slot[i];
 36: }