Standard Template Library Programmer's Guide

copy(A, A + N, ostream_iterator(cout, " "));

// The printed result might be 7 1 6 3 2 5 4 8,

// or any of 40,319 other possibilities.

[1] This algorithm is described in 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 Moses and Oakford (1963) and Durstenfeld (1964). Note that there are N! ways of arranging a sequence of N elements. Random_shuffle yields uniformly distributed results; that is, the probability of any particular ordering is 1/N!. The reason this comment is important is that there are a number of algorithms that seem at first sight to implement random shuffling of a sequence, but that do not in fact produce a uniform distribution over the N! possible orderings. That is, it's easy to get random shuffle wrong.

random_sample , random_sample_n , next_permutation , prev_permutation , Random Number Generator

Category: algorithms

Component type: function

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

template

Random AccessIterator random_sample(InputIterator first, InputIterator last, RandomAccessIterator ofirst, RandomAccessIterator olast)

template

random_sample(InputIterator first, InputIterator last, RandomAccessIterator ofirst, RandomAccessIterator olast, RandomNumberGenerator& rand)

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.

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h. This function is an SGI extension; it is not part of the C++ standard.

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.

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

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

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

random_shuffle , random_sample_n , Random Number Generator

Category: algorithms

Component type: function

Random_sample_n is an overloaded name; there are actually two random_sample_n functions.

template

OutputIterator random_sample_n(ForwardIterator first, ForwardIterator last, OutputIterator out, Distance n)

template

OutputIterator random_sample_n(ForwardIterator first, ForwardIterator last, OutputIterator out, Distance n, RandomNumberGenerator& rand)

Random_sample_n randomly copies a sample of the elements from the range [first, last) into the range [out, out + n) . 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 appear in the same relative order as their relative order within the input range. [2]

Random_sample copies m elements from [first, last) to [out, out + m) , where m is min(last – first, n) . The return value is out + m .

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.

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h. This function is an SGI extension; it is not part of the C++ standard.

For the first version: