The algorithm std::shuffle
of <algorithm>
does exactly what you describe:
template<typename RandomIt, typename Gen>
void shuffle(RandomIt first, RandomIt last, Gen&& 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;
diff_t n = last - first;
for (diff_t i = n-1; i > 0; --i)
{
using std::swap;
swap(first[i], first[D(g, param_t(0, i))]);
}
}
The idea is to iterate the interval [first, last) backwards (i
beginning in n-1
until 1
), exchanging each element in sequence with some other random, which is in the range [0, i].
Example of the use of std::shuffle
:
#include <random>
#include <algorithm>
#include <iterator>
int main()
{
std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// Motor com semente gerada por `rd`.
std::random_device rd;
std::mt19937 g(rd());
// Embaralha o vetor `v` usando o motor de números aleatórios `g`.
std::shuffle(v.begin(), v.end(), g);
// A partir daqui, `v` está com seus elementos embaralhados.
}
I’ve been thinking a little bit about this standard implementation algorithm. It’s very smart.
– Kahler