## random_shuffle

random_shuffle

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.  There are two different versions of random_shuffle. 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.

### 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

 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. 