|
| |
|
| Category: algorithms | | Component type: function |
Prototype
Random_shuffle is an overloaded name; there are actually two random_shuffle functions.
template <class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
RandomNumberGenerator& rand)
Description
Random_shuffle randomly rearranges the elements in the range [first, last): that is, it randomly picks one of the N! possible orderings, where N is last - first. [1] There are two different versions of random_shuffle. The first version uses an internal random number generator, and the second uses a RandomNumberGenerator, a special kind of functors, that is explicitly passed as an argument.
Definition
Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
Requirements on types
For the first version:
For the second version:
-
RandomAccessIterator is a model of RandomAccessIterator
-
RandomNumberGenerator is a model of RandomNumberGenerator
-
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, " "));
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, RandomNumberGenerator
