Como embaralhar um std :: vector?

97

Estou procurando uma maneira genérica e reutilizável de embaralhar um std::vectorem C ++. É assim que eu faço atualmente, mas acho que não é muito eficiente porque precisa de um array intermediário e precisa saber o tipo de item (DeckCard neste exemplo):

srand(time(NULL));

cards_.clear();

while (temp.size() > 0) {
    int idx = rand() % temp.size();
    DeckCard* card = temp[idx];
    cards_.push_back(card);
    temp.erase(temp.begin() + idx);
}
Laurent
fonte
Não. procure pescadores ....
Mitch Wheat
3
Tente não usar rand(), existem melhores APIs RNG disponíveis (Boost.Random ou 0x <random>).
Cat Plus Plus
Vinculado: stackoverflow.com/questions/147391/…
Sardathrion - contra o abuso de SE

Respostas:

201

Do C ++ 11 em diante, você deve preferir:

#include <algorithm>
#include <random>

auto rng = std::default_random_engine {};
std::shuffle(std::begin(cards_), std::end(cards_), rng);

Live example on Coliru

Certifique-se de reutilizar a mesma instância de em rngtodas as chamadas parastd::shuffle se pretende gerar permutações diferentes a cada vez!

Além disso, se quiser que seu programa crie diferentes sequências de embaralhamento cada vez que for executado, você pode semear o construtor do mecanismo aleatório com a saída de std::random_device:

auto rd = std::random_device {}; 
auto rng = std::default_random_engine { rd() };
std::shuffle(std::begin(cards_), std::end(cards_), rng);

Para C ++ 98, você pode usar:

#include <algorithm>

std::random_shuffle(cards_.begin(), cards_.end());
user703016
fonte
8
Você também pode conectar um gerador de números aleatórios personalizado como um terceiro argumento de std::random_shuffle.
Alexandre C.
19
+1 - Observe que isso pode produzir um resultado idêntico a cada execução do programa. Você pode adicionar um gerador de número aleatório personalizado (que pode ser propagado de uma fonte externa) como um argumento adicional std::random_shufflese isso for um problema.
Mankarse
4
@ Gob00st: irá gerar o mesmo resultado para todas as instâncias do programa, não para todas as chamadas para random_shuffle. Este comportamento é normal e intencional.
user703016
3
@ TomášZato#include <algorithm>
user703016
4
@ ParkYoung-Bae Obrigado, acabei de descobrir . É realmente inconveniente quando as respostas do SO não contêm informações incluídas porque estão no topo dos resultados de pesquisa do Google.
Tomáš Zato - Reintegrar Monica
10

http://www.cplusplus.com/reference/algorithm/shuffle/

// shuffle algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::shuffle
#include <vector>       // std::vector
#include <random>       // std::default_random_engine
#include <chrono>       // std::chrono::system_clock

int main () 
{
    // obtain a time-based seed:
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::default_random_engine e(seed);

    while(true)
    {
      std::vector<int> foo{1,2,3,4,5};

      std::shuffle(foo.begin(), foo.end(), e);

      std::cout << "shuffled elements:";
      for (int& x: foo) std::cout << ' ' << x;
      std::cout << '\n';
    }

    return 0;
}
Mehmet Fide
fonte
um exemplo ruim copiado de cplusplus.com/reference/algorithm/shuffle . Como você faz outra chamada de shuffle?
miracle173
@ milagre173 exemplo melhorado
Mehmet Fide
2
Por que o uso estranho do relógio do sistema para uma semente em vez de apenas usar std::random_device?
Chuck Walbourn
6

Além do que @Cicada disse, você provavelmente deve semear primeiro,

srand(unsigned(time(NULL)));
std::random_shuffle(cards_.begin(), cards_.end());

Por comentário de @FredLarson:

a fonte de aleatoriedade para esta versão de random_shuffle () é definida pela implementação, então ele pode não usar rand (). Então srand () não teria efeito.

Então YMMV.


fonte
10
Na verdade, a fonte de aleatoriedade para esta versão do random_shuffle()é definida pela implementação, portanto, ela pode nem ser usada rand(). Então srand()não teria efeito. Já deparei com isso antes.
Fred Larson
@Fred: Obrigado Fred. Não sabia isso. Estou acostumado a usar o srand o tempo todo.
6
Você provavelmente deve excluir esta resposta, pois está errada e - pior ainda - parece correta e de fato está correta em algumas implementações, mas não em todas, tornando este conselho muito perigoso.
Thomas Bonini
2
Como @Fred explicado acima, o que random_shuffleusa para gerar números aleatórios é definido pela implementação. Isso significa que na sua implementação ele usa rand()(e portanto srand () funciona), mas na minha ele pode usar algo totalmente diferente, o que significa que na minha implementação, mesmo com srand, toda vez que executar o programa, obterei os mesmos resultados.
Thomas Bonini
2
@Code: como discutimos, não funciona em todas as implementações. O fato de você poder fornecer sua própria geração de números não é mencionado em sua resposta e, de qualquer forma, não está relacionado a esta discussão. Eu sinto que estamos andando em círculos: S
Thomas Bonini
2

Se você estiver usando boost, você pode usar esta classe ( debug_modeestá definida como false, se você quiser que a randomização seja previsível entre a execução, você deve defini-la como true):

#include <iostream>
#include <ctime>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/uniform_int_distribution.hpp>
#include <boost/random/variate_generator.hpp>
#include <algorithm> // std::random_shuffle

using namespace std;
using namespace boost;

class Randomizer {
private:
    static const bool debug_mode = false;
    random::mt19937 rng_;

    // The private constructor so that the user can not directly instantiate
    Randomizer() {
        if(debug_mode==true){
            this->rng_ = random::mt19937();
        }else{
            this->rng_ = random::mt19937(current_time_nanoseconds());
        }
    };

    int current_time_nanoseconds(){
        struct timespec tm;
        clock_gettime(CLOCK_REALTIME, &tm);
        return tm.tv_nsec;
    }

    // C++ 03
    // ========
    // Dont forget to declare these two. You want to make sure they
    // are unacceptable otherwise you may accidentally get copies of
    // your singleton appearing.
    Randomizer(Randomizer const&);     // Don't Implement
    void operator=(Randomizer const&); // Don't implement

public:
    static Randomizer& get_instance(){
        // The only instance of the class is created at the first call get_instance ()
        // and will be destroyed only when the program exits
        static Randomizer instance;
        return instance;
    }

    template<typename RandomAccessIterator>
    void random_shuffle(RandomAccessIterator first, RandomAccessIterator last){
        boost::variate_generator<boost::mt19937&, boost::uniform_int<> > random_number_shuffler(rng_, boost::uniform_int<>());
        std::random_shuffle(first, last, random_number_shuffler);
    }

    int rand(unsigned int floor, unsigned int ceil){
        random::uniform_int_distribution<> rand_ = random::uniform_int_distribution<> (floor,ceil);
        return (rand_(rng_));
    }
};

Então você pode testá-lo com este código:

#include "Randomizer.h"
#include <iostream>
using namespace std;

int main (int argc, char* argv[]) {
    vector<int> v;
    v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);
    v.push_back(6);v.push_back(7);v.push_back(8);v.push_back(9);v.push_back(10);

    Randomizer::get_instance().random_shuffle(v.begin(), v.end());
    for(unsigned int i=0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    return 0;
}
madx
fonte
Por que você está usando o tempo para semear o gerador em vez de std::random_device?
Chuck Walbourn
1

Pode ser ainda mais simples, a propagação pode ser totalmente evitada:

#include <algorithm>
#include <random>

// Given some container `container`...
std::shuffle(container.begin(), container.end(), std::random_device());

Isso produzirá uma nova ordem aleatória cada vez que o programa for executado. Também gosto dessa abordagem devido à simplicidade do código.

Isso funciona porque tudo o que precisamos std::shuffleé de um UniformRandomBitGenerator, cujos requisitos std::random_deviceatenda.

Nota: se embaralhar repetidamente, pode ser melhor armazenar o random_deviceem uma variável local:

std::random_device rd;
std::shuffle(container.begin(), container.end(), rd);
Apollys apóia Monica
fonte
2
O que isso adiciona que ainda não fazia parte da resposta aceita de 8 anos atrás?
ChrisMM
1
Tudo que você precisa fazer é ler a resposta para descobrir ... Não há muito mais a ser dito que já não tenha sido explicado de forma muito clara acima.
Apollys apoia Monica de
1
A resposta aceita já usa shuffle e diz para usar random_device...
ChrisMM
1
A antiga resposta aceita pode ser mais aprofundada. No entanto, esta é precisamente a resposta pontual de linha única que eu esperaria ao pesquisar no Google por uma pergunta tão simples sem muito esforço. +1
Ichthyo
2
Isso está errado . random_deviceé projetado para ser chamado apenas uma vez para semear PRNGs, não para ser chamado repetidamente (o que pode exaurir a entropia subjacente rapidamente e fazer com que ela mude para um esquema de geração abaixo do ideal)
LF