Definition Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
Requirements on types For the first version:
• RandomAccessIterator is a model of Random Access Iterator
For the second version:
• RandomAccessIterator is a model of Random Access Iterator
• RandomNumberGenerator is a model of Random Number Generator
• RandomAccessIterator's distance type is convertible to RandomNumberGenerator's argument type.
Preconditions • [first, last) is a valid range.
• last – first is less than rand 's maximum value.
Complexity Linear in last – first . If last != first, exactly (last – first) – 1 swaps are performed.
Example const int N = 8;
int A[] = {1, 2, 3, 4, 5, 6, 7, 8};
random_shuffle(A, A + N);
copy(A, A + N, ostream_iterator<int>(cout, ' '));
// The printed result might be 7 1 6 3 2 5 4 8,
// or any of 40,319 other possibilities.
Notes [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.
See also random_sample, random_sample_n, next_permutation, prev_permutation, Random Number Generator
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 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.
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);
