# 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`. [1] 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

[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

Copyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation