Wie mische ich einen std :: vector?

97

Ich suche nach einer generischen, wiederverwendbaren Möglichkeit, a std::vectorin C ++ zu mischen . So mache ich das derzeit, aber ich denke, es ist nicht sehr effizient, da es ein Zwischenarray benötigt und den Elementtyp kennen muss (DeckCard in diesem Beispiel):

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
quelle
Nee. Nachschlagen von Fischern ...
Mitch Wheat
3
Versuchen Sie nicht zu verwenden rand(), es sind bessere RNG-APIs verfügbar (Boost.Random oder 0x <random>).
Cat Plus Plus
Verknüpft: stackoverflow.com/questions/147391/…
Sardathrion - gegen SE-Missbrauch

Antworten:

201

Ab C ++ 11 sollten Sie Folgendes bevorzugen:

#include <algorithm>
#include <random>

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

Live example on Coliru

Stellen Sie sicher, dass Sie dieselbe Instanz rngwährend mehrerer Aufrufe wiederverwenden , std::shufflewenn Sie beabsichtigen, jedes Mal unterschiedliche Permutationen zu generieren!

Wenn Sie möchten, dass Ihr Programm bei jeder Ausführung unterschiedliche Shuffles-Sequenzen erstellt, können Sie den Konstruktor der Zufalls-Engine mit der Ausgabe von std::random_device:

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

Für C ++ 98 können Sie Folgendes verwenden:

#include <algorithm>

std::random_shuffle(cards_.begin(), cards_.end());
user703016
quelle
8
Sie können auch einen benutzerdefinierten Zufallszahlengenerator als drittes Argument von anschließen std::random_shuffle.
Alexandre C.
19
+1 - Beachten Sie, dass dies bei jedem Programmlauf zu einem identischen Ergebnis führen kann. Sie können einen benutzerdefinierten Zufallszahlengenerator (der aus einer externen Quelle erstellt werden kann) als zusätzliches Argument hinzufügen, std::random_shufflewenn dies ein Problem darstellt.
Mankarse
4
@ Gob00st: Es wird für jede Instanz des Programms das gleiche Ergebnis generiert, nicht für jeden Aufruf von random_shuffle. Dieses Verhalten ist normal und beabsichtigt.
user703016
3
@ TomášZato#include <algorithm>
user703016
4
@ ParkYoung-Bae Danke, ich habe es gerade herausgefunden . Es ist wirklich unpraktisch, wenn SO-Antworten keine Include-Informationen enthalten, da sie ganz oben in den Google-Suchergebnissen stehen.
Tomáš Zato - Wiedereinsetzung 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
quelle
Ein schlechtes Beispiel, das von cplusplus.com/reference/algorithm/shuffle kopiert wurde . Wie machst du einen weiteren Shuffle-Anruf?
Wunder173
@ Wunder173 Beispiel verbessert
Mehmet Fide
2
Warum die seltsame Verwendung der Systemuhr für einen Samen, anstatt nur zu verwenden std::random_device?
Chuck Walbourn
6

Zusätzlich zu dem, was @Cicada gesagt hat, sollten Sie wahrscheinlich zuerst säen,

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

Per @ FredLarsons Kommentar:

Die Zufallsquelle für diese Version von random_shuffle () ist implementierungsdefiniert, daher wird möglicherweise rand () überhaupt nicht verwendet. Dann hätte srand () keine Wirkung.

Also YMMV.


quelle
10
Tatsächlich ist die Zufallsquelle für diese Version von random_shuffle()die Implementierung definiert, sodass sie möglicherweise überhaupt nicht verwendet wird rand(). Dann srand()hätte das keine Wirkung. Darauf bin ich schon einmal gestoßen.
Fred Larson
@Fred: Danke Fred. Wusste ich nicht. Ich war es gewohnt, die ganze Zeit srand zu benutzen.
6
Sie sollten diese Antwort wahrscheinlich löschen, da sie falsch ist und - noch schlimmer - sie korrekt erscheint und in einigen Implementierungen tatsächlich korrekt ist, aber nicht in allen, was diesen Rat sehr gefährlich macht.
Thomas Bonini
2
Wie oben erläutert, random_shuffleist die Implementierung definiert, wie @Fred Zufallszahlen generiert. Dies bedeutet, dass bei Ihrer Implementierung rand()(und damit srand () funktioniert), bei meiner jedoch etwas völlig anderes verwendet werden kann, was bedeutet, dass ich bei meiner Implementierung auch mit srand jedes Mal, wenn ich das Programm ausführe, die gleichen Ergebnisse erhalte.
Thomas Bonini
2
@Code: Wie wir bereits besprochen haben, funktioniert es nicht in allen Implementierungen. Die Tatsache, dass Sie Ihre eigene Nummerngenerierung bereitstellen können, wird in Ihrer Antwort nicht erwähnt und steht in keinem Fall in Zusammenhang mit dieser Diskussion. Ich fühle mich wie wir im Kreis gehen: S
Thomas Bonini
2

Wenn Sie Boost verwenden, können Sie diese Klasse verwenden ( debug_modeist auf gesetzt false, wenn Sie möchten, dass die Randomisierung zwischen der Ausführung vorhersehbar ist, müssen Sie sie setzen 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_));
    }
};

Dann können Sie es mit diesem Code testen:

#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
quelle
Warum nutzen Sie die Zeit, um den Generator zu säen, anstatt std::random_device?
Chuck Walbourn
1

Es kann noch einfacher sein, das Säen kann gänzlich vermieden werden:

#include <algorithm>
#include <random>

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

Dies erzeugt jedes Mal, wenn das Programm ausgeführt wird, eine neue Zufallswiedergabe. Ich mag diesen Ansatz auch wegen der Einfachheit des Codes.

Dies funktioniert , weil alles , was wir brauchen für std::shuffleeine ist UniformRandomBitGenerator, die Anforderungen std::random_deviceerfüllt.

Hinweis: Wenn Sie wiederholt mischen, ist es möglicherweise besser, die random_devicein einer lokalen Variablen zu speichern :

std::random_device rd;
std::shuffle(container.begin(), container.end(), rd);
Apollys unterstützt Monica
quelle
2
Was fügt dies hinzu, das nicht bereits Teil der akzeptierten Antwort von vor 8 Jahren war?
ChrisMM
1
Alles, was Sie tun müssen, ist die Antwort zu lesen, um herauszufinden ... Es gibt nicht viel mehr zu sagen, was oben noch nicht sehr klar erklärt wurde.
Apollys unterstützt Monica
1
Die akzeptierte Antwort verwendet bereits Shuffle und sagt zu verwenden random_device...
ChrisMM
1
Die alte akzeptierte Antwort könnte ausführlicher sein. Dies ist jedoch genau die einzeilige Point-and-Shot-Antwort, die ich erwarten würde, wenn ich ohne viel Aufhebens nach einer so einfachen Frage google. +1
Ichthyo
2
Das ist falsch . random_devicewurde entwickelt, um nur einmal aufgerufen zu werden, um PRNGs zu säen, und nicht, um immer wieder aufgerufen zu werden (was die zugrunde liegende Entropie schnell erschöpfen und dazu führen kann, dass sie zu einem suboptimalen Generierungsschema wechselt)
LF