std::shuffle() algorithm

od C++11

// (1)
template< class RandomIt, class URBG >
void shuffle( RandomIt first, RandomIt last, URBG&& g );

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

Parameters

first last	The range of elements to shuffle.
g	A UniformRandomBitGenerator whose result type is convertible to std::iterator_traits<RandomIt>::difference_type.

Type requirements

RandomIt	LegacyRandomAccessIterator ValueSwappable
std::remove_reference_t<URBG>	UniformRandomBitGenerator

Return value

(none)

Complexity

Linear in std::distance(first, last);

Exceptions

(none)

Possible implementation

shuffle (1)

template<class RandomIt>
template<class RandomIt, class URBG>
void shuffle(RandomIt first, RandomIt last, URBG&& g)
{
    using diff_t = typename std::iterator_traits<RandomIt>::difference_type;
    using distr_t = std::uniform_int_distribution<diff_t>;
    using param_t = typename distr_t::param_type;

    distr_t D;
    for (diff_t i = last - first - 1; i > 0; --i)
    {
        using std::swap;
        swap(first[i], first[D(g, param_t(0, i))]);
    }
}

Notes

Note that the implementation is not dictated by the standard, so even if you use exactly the same or URBG (Uniform Random Number Generator) you may get different results with different standard library implementations.

Main.cpp

#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>

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);

    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
}

Possible Output

5 2 1 4 6 3 7 10 9 8