How to Randomize an Array in C ++

0

There is a lot of stuff here about array ordering methods (quicksort, bubblesort, etc.), but I was wondering if there is a method of "cluttering" arrays, that is, shuffling the array elements. >

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

** Please, besides showing the algorithm, could you explain the logic behind it?

    
asked by anonymous 15.05.2018 / 00:05

2 answers

2

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.
}
    
15.05.2018 / 15:07
1

Cluttering a set of elements is not as common an operation as ordering, so it is not such a recurring subject.

Here is an example of an algorithm for shuffling a vector:

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 randomly indexing a vector, extracting one element at a time, until it is empty.

This online example shows the output when you apply it to a vector of string s:

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 just gave you an algorithm example, as you requested. In practice, there are more efficient and recommended methods, including a function in the std library, the std::shuffle

    
15.05.2018 / 07:20