Normalmente estudamos algoritmos para ordenar vetores, mas dificilmente para embaralhar. Apesar disso existem dois STL Algorithms para embaralhar containers não ordenados. Obviamente esses algoritmos não funcionam com containers ordenados, como std::map, std::set ou std::list, por exemplo, mas funciona muito bem com std::vector, ou mesmo arrays padrão C.

Números Randômicos

Primeiro vamos explicar que não existe geração de números 100% randômicos, o que existe são algoritmos que geram sequências que se parecem muito com randômicos, para aumentar a característica randômica adiciona-se um valor inicial, uma semente, melhorando o resultado.

Em C temos duas funções que geram números randômicos. srand() inicializa a semente randômica, normalmente utilizamos time(NULL) como parâmetro, assim cada execução irá inicializar uma sequência de números pseudo randômicos. A outra função é rand(), que gera um número randômico entre 0 e a constante RAND_MAX, por definição maior que 32.767. Vamos a um exemplo simples:

#include <cstdlib>
#include <iostream>
int main() {
    ::srand (time(NULL));
    int d6 = rand() % 6;              // randomizar de 0 a 5
    int d8 = rand() % 8 + 1;          // randomizar de 1 a 4
    int eightys = rand() % 10 + 1981; // randomizar de 1981 a 1990
}

Note como é possível randomizar entre 0 e RAND_MAX, mas também é muito simples randomizar entre qualquer faixa de valores.

C++03: std::shuffle_random

O algoritmo shuffle passou por uma revisão recentemente. Pra quem usa até C++03, é essencial utilizar std::shuffle_random, já para quem usa a partir de C++11 é melhor utilizar a opção mais moderna std::shuffle.

Primeiro um exemplo de utilização do std::shuffle_random:

#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>
void coutfn(int i) { std::cout << i << " "; }
int randomize(int i) { return rand() % i; }
int main() {
    ::srand(::time(NULL));
    int a[] = {1, 2, 3, 4, 5};
    std::vector<int> v(4);
    v[0] = 0; v[1] = 1;
    v[2] = 2; v[3] = 3;

    std::cout << "Before shuffle..." << std::endl;
    std::for_each(&a[0], &a[4], coutfn);
    std::cout << std::endl;
    std::for_each(v.begin(), v.end(), coutfn);
    std::cout << std::endl;

    std::random_shuffle(&a[0], &a[4]);
    std::random_shuffle(v.begin(), v.end(), randomize);

    std::cout << std::endl << "After shuffle..." << std::endl;
    std::for_each(&a[0], &a[4], coutfn);
    std::cout << std::endl;
    std::for_each(v.begin(), v.end(), coutfn);
}

Note que da primeira vez que chamamos std::shuffle_random os únicos argumentos são o início e o final da faixa do array. Já na segunda chamada utilizamos uma função que gera a randomização do shuffle.

Para entender melhor como usar a função de randomização do std::shuffle_random, é melhor entendermos o algoritmo por trás da função:

template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle (
    RandomAccessIterator first, 
    RandomAccessIterator last,
    RandomNumberGenerator& gen
) {
  iterator_traits<RandomAccessIterator>::difference_type i, n;
  n = (last-first);
  for (i = n - 1; i > 0; --i)
    swap(first[i], first[gen(i + 1)]);
}

Portanto a função de randomização irá selecionar qual será o elemento que será trocado com o atual, enquanto percorre o container item por item.

Note que std::shuffle_random não é mais válido para C++17, sobrando a utilização do std::shuffle.

C++11: std::shuffle

Pouca diferença no código para usar std::shuffle:

#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
void coutfn(int i) { std::cout << i << " "; }
int randomize(int i) { return rand() % i; }
int main() {
    int a[] = {1, 2, 3, 4, 5};
    std::vector<int> v(4);
    v[0] = 0; v[1] = 1;
    v[2] = 2; v[3] = 3;


    std::cout << "Before shuffle..." << std::endl;
    std::for_each(&a[0], &a[4], coutfn);
    std::cout << std::endl;
    std::for_each(v.begin(), v.end(), coutfn);
    std::cout << std::endl;

    auto seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::shuffle(&a[0], &a[4], std::default_random_engine(seed));
    std::shuffle(v.begin(), v.end(), std::default_random_engine(seed));

    std::cout << std::endl << "After shuffle..." << std::endl;
    std::for_each(&a[0], &a[4], coutfn);
    std::cout << std::endl;
    std::for_each(v.begin(), v.end(), coutfn);
}

Note as semelhanças do código. A grande diferença dos dois códigos de exemplo está na utilização de classes e funções disponíveis a partir do C++11, como as bibliotecas chrono e radom.

No demais o funcionamento é equivalente.

Na Prática

Na prática não é tão comum precisarmos randomizar ou embaralhar, da mesma forma não é comum haver políticas específicas para a utilização das funções de shuffle.

Em C++11 a biblioteca random oferece uma grande variedade de formas para gerar números randômicos ou pseudo-randômicos. Quando disponível é sempre recomendado utilizá-las. Vamos abordar essa biblioteca da STL em um post futuro.

Tags: c++, STL, STL Algorithms