Category: algorithms | Component type: function |
template <class InputIterator, class RandomAccessIterator> Random AccessIterator random_sample(InputIterator first, InputIterator last, RandomAccessIterator ofirst, RandomAccessIterator olast) template <class InputIterator, class RandomAccessIterator, class RandomNumberGenerator> random_sample(InputIterator first, InputIterator last, RandomAccessIterator ofirst, RandomAccessIterator olast, RandomNumberGenerator& rand)
Random_sample copies n elements from [first, last) to [ofirst, olast), where n is min(last - first, olast - ofirst). The return value is ofirst + n.
The first version uses an internal random number generator, and the second uses a Random Number Generator, a special kind of function object, that is explicitly passed as an argument.
int main() { const int N = 10; const int n = 4; int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int B[n]; random_sample(A, A+N, B, B+n); copy(B, B + n, ostream_iterator<int>(cout, " ")); // The printed value might be 1 6 3 5, // or any of 5039 other possibilities. }
[1] This is "Algorithm R" from section 3.4.2 of Knuth (D. E. Knuth, The Art of Computer Programming. Volume 2: Seminumerical Algorithms, second edition. Addison-Wesley, 1981). Knuth credits Alan Waterman. Note that there are N! / n! / (N - n)! ways of selecting a sample of n elements from a range of N elements. Random_sample yields uniformly distributed results; that is, the probability of selecting any particular element is n / N, and the probability of any particular sampling (not considering order of elements) is n! * (N - n)! / N!.
[2] If preservation of the relative ordering within the input range is important for your application, you should use random_sample_n instead. The main restriction of random_sample_n is that the input range must consist of Forward Iterators, rather than Input Iterators.