Jak przetasować std :: vector?

97

Szukam ogólnego, wielokrotnego użytku sposobu na przetasowanie std::vectorw C ++. Tak to teraz robię, ale myślę, że nie jest to zbyt wydajne, ponieważ wymaga tablicy pośredniej i musi znać typ elementu (w tym przykładzie DeckCard):

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
źródło
nie. look up fisher-yates…
Mitch Wheat
3
Staraj się nie używać rand(), dostępne są lepsze API RNG (Boost.Random lub 0x <random>).
Cat Plus Plus
Powiązane: stackoverflow.com/questions/147391/…
Sardathrion - przeciwko nadużyciom SE

Odpowiedzi:

201

Począwszy od C ++ 11, powinieneś preferować:

#include <algorithm>
#include <random>

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

Live example on Coliru

Jeśli zamierzasz za każdym razem generować różne permutacje, pamiętaj o ponownym użyciu tego samego wystąpienia rngpodczas wielu wywołań programu std::shuffle!

Ponadto, jeśli chcesz, aby Twój program tworzył różne sekwencje tasowań za każdym razem, gdy jest uruchamiany, możesz zaszczepić konstruktor silnika losowego z wynikiem std::random_device:

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

W przypadku C ++ 98 możesz użyć:

#include <algorithm>

std::random_shuffle(cards_.begin(), cards_.end());
user703016
źródło
8
Możesz także podłączyć niestandardowy generator liczb losowych jako trzeci argument funkcji std::random_shuffle.
Alexandre C.
19
+1 - Zauważ, że może to dać identyczny wynik przy każdym uruchomieniu programu. Możesz dodać niestandardowy generator liczb losowych (który może być zainicjowany z zewnętrznego źródła) jako dodatkowy argument, std::random_shufflejeśli stanowi to problem.
Mankarse
4
@ Gob00st: wygeneruje ten sam wynik dla każdej instancji programu, a nie dla każdego wywołania random_shuffle. To zachowanie jest normalne i zamierzone.
user703016
3
@ TomášZato#include <algorithm>
user703016
4
@ ParkYoung-Bae Dzięki, właśnie się dowiedziałem . To naprawdę niewygodne, gdy odpowiedzi SO nie zawierają informacji, ponieważ znajdują się one na górze wyników wyszukiwania Google.
Tomáš Zato - Przywróć Monikę
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
źródło
zły przykład skopiowany z cplusplus.com/reference/algorithm/shuffle . Jak wykonać kolejną rozmowę losową?
cud173
Przykład @ miracle173 poprawiony
Mehmet Fide
2
Po co dziwne używanie zegara systemowego do zarodka zamiast po prostu używać std::random_device?
Chuck Walbourn,
6

Oprócz tego, co powiedział @Cicada, prawdopodobnie powinieneś najpierw wysiać,

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

Komentarz Per @ FredLarson:

źródło losowości dla tej wersji random_shuffle () jest zdefiniowane w implementacji, więc może w ogóle nie używać rand (). Wtedy srand () nie miałoby żadnego efektu.

Więc YMMV.


źródło
11
W rzeczywistości źródłem losowości dla tej wersji random_shuffle()jest zdefiniowana implementacja, więc może rand()w ogóle nie używać . Wtedy srand()nie miałoby to żadnego skutku. Spotkałem się z tym wcześniej.
Fred Larson
@Fred: Dzięki Fred. Nie wiedział tego. Przez cały czas byłem przyzwyczajony do używania srand.
6
Prawdopodobnie powinieneś usunąć tę odpowiedź, ponieważ jest błędna i - co gorsza - wydaje się poprawna i rzeczywiście jest poprawna w niektórych implementacjach, ale nie we wszystkich, co czyni tę poradę bardzo niebezpieczną.
Thomas Bonini,
2
Jak wyjaśnił @Fred powyżej, to, co random_shufflesłuży do generowania liczby losowej, jest zdefiniowane jako implementacja. Oznacza to, że w twojej implementacji używa rand()(i dlatego srand () działa), ale na mojej może używać czegoś zupełnie innego, co oznacza, że ​​na mojej implementacji nawet z srand za każdym razem, gdy uruchomię program, uzyskam te same wyniki.
Thomas Bonini,
2
@Code: tak jak omówiliśmy, nie działa we wszystkich implementacjach. Fakt, że możesz podać własne generowanie liczb, nie jest wspomniany w Twojej odpowiedzi i nie ma związku z tą dyskusją w żadnym przypadku. Czuję, że kręcimy się w kółko: S
Thomas Bonini
2

Jeśli używasz doładowania, możesz użyć tej klasy ( debug_modejest ustawiona na false, jeśli chcesz, aby randomizacja była przewidywalna między wykonaniem, musisz ją ustawić 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_));
    }
};

Możesz to przetestować tym kodem:

#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
źródło
Dlaczego wykorzystujesz czas do zasiania generatora zamiast std::random_device?
Chuck Walbourn,
1

Może być jeszcze prostsze, można całkowicie uniknąć wysiewu:

#include <algorithm>
#include <random>

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

Spowoduje to utworzenie nowego tasowania przy każdym uruchomieniu programu. Podoba mi się również to podejście ze względu na prostotę kodu.

To działa, ponieważ wszystko, czego potrzebujemy, std::shuffleto a UniformRandomBitGenerator, którego wymagania std::random_devicespełniają.

Uwaga: w przypadku wielokrotnego tasowania może być lepiej przechowywać random_devicew zmiennej lokalnej:

std::random_device rd;
std::shuffle(container.begin(), container.end(), rd);
Apollys wspiera Monikę
źródło
2
Co to dodaje, czego nie było już w akceptowanej odpowiedzi sprzed 8 lat?
ChrisMM
1
Wszystko, co musisz zrobić, to przeczytać odpowiedź, aby się dowiedzieć ... Niewiele więcej można powiedzieć, co nie zostało jeszcze jasno wyjaśnione powyżej.
Apollys wspiera Monikę
1
Zaakceptowana odpowiedź już używa random_device
odtwarzania
1
Stara akceptowana odpowiedź może być bardziej szczegółowa. Jest to jednak dokładnie ta pojedyncza odpowiedź, której bym się spodziewał, szukając w Google tak prostego pytania bez zbędnych ceregieli. +1
Ichthyo
2
To jest złe . random_devicejest zaprojektowany tak, aby był wywoływany tylko raz w celu zaszczepienia PRNG, nie może być wywoływany w kółko (co może szybko wyczerpać podstawową entropię i spowodować przejście do schematu generowania suboptymalnego)
LF