How to randomize an Array in c++

Question

There is a lot of material here about arrays ordering methods (quicksort, bubblesort, etc.) but I wanted to know if there is a "clutter" method of arrays, i.e., shuffling the elements of an array.

*There are even questions here about this theme, but they are about java or C#.

**Please, besides showing the algorithm, it would have to explain the logic behind ?

Answer 1

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.
}

Answer 2

Clutter a set of elements is not as common an operation as order, so it is not so recurrent subject.

Here is an example of an algorithm for shuffling an array:

template <typename T>
std::vector<T> geraDesordenado(std::vector<T> V)
{
    static std::mt19937 G(42); //gerador de números aleatórios
    std::vector<T> R; //buffer de resultado
    while(!V.empty())
    {
        std::uniform_int_distribution<std::size_t> 
             d(0, V.size()-1); //probabilidade linear entre índices restantes (de zero até tamanho-1)
        auto i = V.begin()+d(G); //gera iterador para posição sorteada
        R.push_back(*i); //copia elemento sorteado
        V.erase(i);      //apaga elemento sorteado
    }
    return R;
}

It works by drawing random indices from a vector, extracting one element at a time, until it empties it.

This online example shows the output when applying it to a vector of strings:

Vetor original:
  Quanta ordem entre dois coelhos? 
Exemplos desordenados:
  ordem coelhos? dois Quanta entre 
  dois entre ordem Quanta coelhos? 
  Quanta ordem entre dois coelhos? 

Well, this code I made just to provide you with an example algorithm, as you requested. In practice, there are more efficient and recommended methods, including a function in the library std, to std::shuffle