std::random_shuffle, std::shuffle

From Cppreference

Jump to: navigation, search

Defined in header `<algorithm>`

template< class RandomAccessIterator > void random_shuffle( RandomAccessIterator first, RandomAccessIterator last );	(1)

template< class RandomAccessIterator, class RandomNumberGenerator > void random_shuffle( RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& r ); template< class RandomAccessIterator, class RandomNumberGenerator > void random_shuffle( RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator&& r );	(2)	(pre-C++11 version) (C++11 version)

template< class RandomAccessIterator, class UniformRandomNumberGenerator > void shuffle( RandomAccessIterator first, RandomAccessIterator last, UniformRandomNumberGenerator&& g );	(3)	(C++11 feature)

Reorders the elements in the given range [first, last) such that each possible permutation of those elements has equal probability of appearance.

1) The random number generator is implementation-defined, the rand function may be used.

2) The random number generator is the function object r.

3) The random number generator is the function object g.

`first, last`	-	the range of elements to shuffle randomly
`r`	-	function object returning a randomly chosen value of type `iterator_traits<RandomAccessIterator>::difference_type` in the interval [0,n) if invoked as `r(n)`
`g`	-	function object returning a randomly chosen value of type `UniformRandomNumberGenerator::result_type` in the interval [g.min(), g.max()] if invoked as `g()` (intended to be used with uniform random number generators from the standard library)

[edit] Return value

(none)

[edit] Complexity

linear in the distance between first and last

[edit] Equivalent function

First version

template<class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, 
                    RandomNumberGenerator&& r)
{
    typename std::iterator_traits<RandomAccessIterator>::difference_type i, n;
    n = last - first;
    for (i = n-1; i > 0; --i) {
        std::swap(first[i], first[r(i+1)]);
    }
}

Second version

template<class RandomAccessIterator, class UniformRandomNumberGenerator>
void shuffle(RandomAccessIterator first, RandomAccessIterator last, 
             UniformRandomNumberGenerator&& g)
{
    typedef typename std::iterator_traits<RandomAccessIterator>::difference_type diff_t;
    typedef typename std::make_unsigned<diff_t>::type udiff_t;
    typedef typename std::uniform_int_distribution<udiff_t> distr_t;
    typedef typename distr_t::param_type param_t;
 
    distr_t D;
    diff_t n = last - first;
    for (diff_t i = n-1; i > 0; --i) {
        std::swap(first[i], first[D(g, param_t(0, i))]);
    }
}

[edit] Example

The following code randomly shuffles the integers 1..10

#include <random>
#include <algorithm>
#include <iterator>
#include <iostream>
 
int main()
{
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
 
    std::random_device rd;
    std::mt19937 g(rd());
 
    std::shuffle(v.begin(), v.end(), g);
 
    copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
}

Output:

8 6 10 4 2 3 7 1 9 5

[edit] See also

next_permutation

generates the next greater lexicographic permutation of a range of elements
(function template)

prev_permutation

generates the next smaller lexicographic permutation of a range of elements
(function template)