Hoe shuffle je een std::vector?

Ik ben op zoek naar een generieke, herbruikbare manier om een std::vectorin C++ te shufflen. Dit is hoe ik het momenteel doe, maar ik denk dat het niet erg efficiënt is omdat het een tussenliggende array nodig heeft en het itemtype moet weten (DeckCard in dit voorbeeld):

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);
}

Antwoord 1, autoriteit 100%

Vanaf C++11 zou u de voorkeur moeten geven aan:

#include <algorithm>
#include <random>
auto rng = std::default_random_engine {};
std::shuffle(std::begin(cards_), std::end(cards_), rng);

Live voorbeeld op Coliru

Zorg ervoor dat u dezelfde instantie van rnghergebruikt bij meerdere aanroepen naar std::shuffleals u van plan bent elke keer verschillende permutaties te genereren!

Bovendien, als u wilt dat uw programma elke keer dat het wordt uitgevoerd verschillende reeksen shuffles maakt, kunt u de constructor van de willekeurige engine seeden met de uitvoer van std::random_device:

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

Voor C++98 kunt u het volgende gebruiken:

#include <algorithm>
std::random_shuffle(cards_.begin(), cards_.end());

Antwoord 2, autoriteit 5%

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;
}

Antwoord 3, autoriteit 3%

Naast wat @Cicada zei, moet je waarschijnlijk eerst seeden,

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

Per opmerking van @FredLarson:

de bron van willekeur voor deze versie van random_shuffle() is
implementatie gedefinieerd, dus het mag helemaal geen rand() gebruiken. Dan srand()
zou geen effect hebben.

Dus YMMV.

Antwoord 4

Als u boostgebruikt, kunt u deze klasse gebruiken (debug_modeis ingesteld naar false, als u wilt dat de randomisatie voorspelbaar kan zijn tussen de uitvoering, moet u deze instellen op 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_));
    }
};

Dan kun je het testen met deze 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;
}

Antwoord 5

Het kan nog eenvoudiger, seeding kan volledig worden vermeden:

#include <algorithm>
#include <random>
// Given some container `container`...
std::shuffle(container.begin(), container.end(), std::random_device());

Dit zal elke keer dat het programma wordt uitgevoerd een nieuwe shuffle produceren. Ik hou ook van deze aanpak vanwege de eenvoud van de code.

Dit werkt omdat alles wat we nodig hebben voor std::shuffleis een UniformRandomBitGenerator, wiens vereisten std::random_devicevoldoen .

Opmerking: als je herhaaldelijk schudt, is het misschien beter om de random_deviceop te slaan in een lokale variabele:

std::random_device rd;
std::shuffle(container.begin(), container.end(), rd);

Antwoord 6

Afhankelijk van de standaard die u moet volgen (C++11/C++14/C++17) biedt deze “cppreference”-pagina behoorlijk goede voorbeelden: https://en.cppreference.com/w/cpp/algorithm/random_shuffle.