Comment mélanger un std :: vector?

97

Je recherche un moyen générique et réutilisable de mélanger un std::vectoren C ++. C'est comme ça que je le fais actuellement, mais je pense que ce n'est pas très efficace car il a besoin d'un tableau intermédiaire et il a besoin de connaître le type d'élément (DeckCard dans cet exemple):

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
la source
Nan. chercher des pêcheurs ...
Mitch Wheat
3
Essayez de ne pas utiliser rand(), il existe de meilleures API RNG disponibles (Boost.Random ou 0x <random>).
Cat Plus Plus
Lié: stackoverflow.com/questions/147391/…
Sardathrion - contre les abus SE

Réponses:

201

À partir de C ++ 11, vous devriez préférer:

#include <algorithm>
#include <random>

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

Live example on Coliru

Assurez-vous de réutiliser la même instance de rngtout au long de plusieurs appels à std::shufflesi vous avez l'intention de générer des permutations différentes à chaque fois!

De plus, si vous voulez que votre programme crée différentes séquences de shuffles à chaque fois qu'il est exécuté, vous pouvez amorcer le constructeur du moteur aléatoire avec la sortie 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);

Pour C ++ 98, vous pouvez utiliser:

#include <algorithm>

std::random_shuffle(cards_.begin(), cards_.end());
utilisateur703016
la source
8
Vous pouvez également brancher un générateur de nombres aléatoires personnalisé comme troisième argument de std::random_shuffle.
Alexandre C.
19
+1 - Notez que cela peut produire un résultat identique à chaque exécution du programme. Vous pouvez ajouter un générateur de nombres aléatoires personnalisé (qui peut être amorcé à partir d'une source externe) comme argument supplémentaire pour déterminer std::random_shufflesi cela pose un problème.
Mankarse
4
@ Gob00st: il générera le même résultat pour chaque instance du programme, pas pour chaque appel à random_shuffle. Ce comportement est normal et intentionnel.
user703016
3
@ TomášZato#include <algorithm>
user703016
4
@ ParkYoung-Bae Merci, je viens de le découvrir . C'est vraiment gênant lorsque les réponses SO ne contiennent pas d'informations, car elles sont en haut des résultats de recherche Google.
Tomáš Zato - Réintégrer 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
la source
un mauvais exemple copié de cplusplus.com/reference/algorithm/shuffle . Comment faire un autre appel de shuffle?
miracle173
@ miracle173 exemple amélioré
Mehmet Fide
2
Pourquoi l'utilisation étrange de l'horloge système pour une graine au lieu de simplement l'utiliser std::random_device?
Chuck Walbourn
6

En plus de ce que @Cicada a dit, vous devriez probablement commencer par semer,

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

Selon le commentaire de @ FredLarson:

la source du caractère aléatoire pour cette version de random_shuffle () est définie par l'implémentation, donc elle ne peut pas utiliser du tout rand (). Alors srand () n'aurait aucun effet.

Alors YMMV.


la source
10
En fait, la source du caractère aléatoire de cette version de random_shuffle()est définie par l'implémentation, elle ne peut donc pas être utilisée rand()du tout. Cela srand()n'aurait alors aucun effet. J'ai déjà rencontré ça.
Fred Larson
@Fred: Merci Fred. Ne savais pas ça. J'ai l'habitude d'utiliser srand tout le temps.
6
Vous devriez probablement supprimer cette réponse car elle est fausse et - pire encore - elle semble correcte et est en effet correcte dans certaines implémentations, mais pas toutes, ce qui rend ce conseil très dangereux.
Thomas Bonini
2
Comme @Fred l'a expliqué ci-dessus, ce qui random_shuffleutilise pour générer un nombre aléatoire est défini par l'implémentation. Cela signifie que sur votre implémentation, il utiliserand() (et donc srand () fonctionne) mais sur le mien, il peut utiliser quelque chose de totalement différent, ce qui signifie que sur mon implémentation, même avec srand, chaque fois que je lance le programme, j'obtiendrai les mêmes résultats.
Thomas Bonini
2
@Code: comme nous en avons discuté, cela ne fonctionne pas dans toutes les implémentations. Le fait que vous puissiez fournir votre propre génération de nombres n'est pas mentionné dans votre réponse et n'est en aucun cas lié à cette discussion. J'ai l'impression que nous tournons en rond: S
Thomas Bonini
2

Si vous utilisez boost, vous pouvez utiliser cette classe ( debug_modedéfinie sur false, si vous voulez que la randomisation soit prévisible entre les exécutions, vous devez la définir sur 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_));
    }
};

Ensuite, vous pouvez le tester avec ce code:

#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
la source
Pourquoi utilisez-vous le temps pour semer le générateur au lieu de std::random_device?
Chuck Walbourn
1

Cela peut être encore plus simple, l'ensemencement peut être totalement évité:

#include <algorithm>
#include <random>

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

Cela produira un nouveau mélange à chaque fois que le programme est exécuté. J'aime aussi cette approche en raison de la simplicité du code.

Cela fonctionne parce que tout ce dont nous avons besoin std::shuffleest un UniformRandomBitGenerator, dont les exigencesstd::random_device répondent.

Remarque: en cas de lecture aléatoire répétée, il peut être préférable de stocker le random_devicedans une variable locale:

std::random_device rd;
std::shuffle(container.begin(), container.end(), rd);
Apollys soutient Monica
la source
2
Qu'est-ce que cela ajoute qui ne faisait pas déjà partie de la réponse acceptée d'il y a 8 ans?
ChrisMM
1
Tout ce que vous avez à faire est de lire la réponse pour le savoir ... Il n'y a pas grand-chose à dire qui n'ait déjà été très clairement expliqué ci-dessus.
Apollys soutient Monica
1
La réponse acceptée utilise déjà la random_device
lecture
1
La vieille réponse acceptée pourrait être plus approfondie. Cependant, c'est précisément la réponse ponctuelle sur une seule ligne à laquelle je m'attendrais lorsque je cherche une question aussi simple sur Google sans trop de temps. +1
Ichthyo
2
C'est faux . random_deviceest conçu pour être appelé une seule fois pour semer les PRNG, pour ne pas être appelé encore et encore (ce qui peut épuiser rapidement l'entropie sous-jacente et la faire passer à un schéma de génération sous-optimal)
LF