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
starting from n-1
to 1
), changing each element in sequence with some other random, that is in the interval [0, i].
Example of using 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.
}