random_sample


Category: algorithms	Component type: function

Prototype

Random_sample is an overloaded name; there are actually two random_sample functions.

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)

Description

Random_sample randomly copies a sample of the elements from the range [first, last) into the range [ofirst, olast). Each element in the input range appears at most once in the output range, and samples are chosen with uniform probability. [1] Elements in the output range might appear in any order: relative order within the input range is not guaranteed to be preserved. [2]

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.

Definition

Defined in algo.h.

Requirements on types

For the first version:

InputIterator is a model of Input Iterator
RandomAccessIterator is a model of Random Access Iterator
RandomAccessIterator is mutable.
InputIterator's value type is convertible to RandomAccessIterator's value type.

For the second version:

InputIterator is a model of Input Iterator
RandomAccessIterator is a model of Random Access Iterator
RandomAccessIterator is mutable.
RandomNumberGenerator is a model of Random Number Generator
InputIterator's value type is convertible to RandomAccessIterator's value type.
RandomAccessIterator's distance type is convertible to RandomNumberGenerator's argument type.

Preconditions

[first, last) is a valid range.
[ofirst, olast) is a valid range.
[first, last) and [ofirst, olast) do not overlap.
last - first is less than rand's maximum value.

Complexity

Linear in last - first. At most last - first elements are copied from the input range to the output range.

Example

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.
}

Notes

[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.