
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. AddisonWesley, 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.
Contact Us  Site Map  Trademarks  Privacy  Using this site means you accept its Terms of Use 
Copyright © 2009  2017 Silicon Graphics International. All rights reserved. 