Algorithm for sampling without replacement?

by

Here’s some code for sampling without replacement based on Algorithm 3.4.2S of Knuth’s book Seminumeric Algorithms.

void SampleWithoutReplacement
(
    int populationSize,    // size of set sampling from
    int sampleSize,        // size of each sample
    vector<int> & samples  // output, zero-offset indicies to selected items
)
{
    // Use Knuth's variable names
    int& n = sampleSize;
    int& N = populationSize;

    int t = 0; // total input records dealt with
    int m = 0; // number of items selected so far
    double u;

    while (m < n)
    {
        u = GetUniform(); // call a uniform(0,1) random number generator

        if ( (N - t)*u >= n - m )
        {
            t++;
        }
        else
        {
            samples[m] = t;
            t++; m++;
        }
    }
}

There is a more efficient but more complex method by Jeffrey Scott Vitter in “An Efficient Algorithm for Sequential Random Sampling,” ACM Transactions on Mathematical Software, 13(1), March 1987, 58-67.

More Related Contents:

  1. Select k random elements from a list whose elements have weights
  2. Quicksort: Choosing the pivot
  3. “On-line” (iterator) algorithms for estimating statistical median, mode, skewness, kurtosis?
  4. Find the paths between two given nodes?
  5. 3D Least Squares Plane
  6. Two Rectangles intersection
  7. help in the Donalds B. Johnson’s algorithm, i cannot understand the pseudo code (PART II)
  8. Algorithms vs OOP [closed]
  9. Find largest rectangle containing only zeros in an N×N binary matrix
  10. Looping in a spiral
  11. Find running median from a stream of integers
  12. How to find the lowest common ancestor of two nodes in any binary tree?
  13. Possible Interview Question: How to Find All Overlapping Intervals
  14. Time complexity of Sieve of Eratosthenes algorithm
  15. Worst case for QuickSort – when can it occur?
  16. Find the set of largest contiguous rectangles to cover multiple areas [duplicate]
  17. Box stacking problem
  18. How to design an algorithm to calculate countdown style maths number puzzle
  19. What are good examples of genetic algorithms/genetic programming solutions? [closed]
  20. How do I find a factorial? [closed]
  21. Creating a random number generator from a coin toss
  22. Randomly Generate Letters According to their Frequency of Use?
  23. What is a loop invariant?
  24. How to express tetration function, for complex numbers
  25. Why does the greedy coin change algorithm not work for some coin sets?
  26. Quicksort superiority over Heap Sort
  27. Why DFS and not BFS for finding cycle in graphs
  28. How do ASCII art image conversion algorithms work? [closed]
  29. Reason for the number 5381 in the DJB hash function?
  30. What is the best algorithm for finding the closest color in an array to another color? [closed]

Leave a Comment