 

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 backwardcompatibility 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. AddisonWesley, 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