ChatGPT解决这个技术问题 Extra ChatGPT

How to shuffle a std::vector?

I am looking for a generic, reusable way to shuffle a std::vector in C++. This is how I currently do it, but I think it's not very efficient because it needs an intermediate array and it needs to know the item type (DeckCard in this example):

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);
}
nope. look up fisher-yates....
Try not to use rand(), there are better RNG APIs available (Boost.Random or 0x <random>).

u
user703016

From C++11 onwards, you should prefer:

#include <algorithm>
#include <random>

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

Live example on Coliru

Make sure to reuse the same instance of rng throughout multiple calls to std::shuffle if you intend to generate different permutations every time!

Moreover, if you want your program to create different sequences of shuffles each time it is run, you can seed the constructor of the random engine with the output of std::random_device:

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

For C++98 you may use:

#include <algorithm>

std::random_shuffle(cards_.begin(), cards_.end());

You can also plug a custom random number generator as a third argument of std::random_shuffle.
+1 - Note that this may produce an identical result every run of the program. You can add a custom random number generator (which can be seeded from an external source) as an additional argument to std::random_shuffle if this is a problem.
@Gob00st: it will generate the same result for every instance of the program, not every call to random_shuffle. This behavior is normal and intended.
@ParkYoung-Bae Thanks, I just found out. It's really inconvenient when SO answers do not contain include info because their are on the top of google search results.
I think you should add how to seed this to your answer. A lot of people (that's me) come here because they googled "c++, shuffle vector".
M
Mehmet Fide

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

a bad example copied from cplusplus.com/reference/algorithm/shuffle . How do you make another call of shuffle?
@miracle173 example improved
Why the weird use of the system clock for a seed instead of just using std::random_device?
佚名

In addition to what @Cicada said, you should probably seed first,

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

Per @FredLarson's comment:

the source of randomness for this version of random_shuffle() is implementation defined, so it may not use rand() at all. Then srand() would have no effect.

So YMMV.


Actually, the source of randomness for this version of random_shuffle() is implementation defined, so it may not use rand() at all. Then srand() would have no effect. I've run into that before.
@Fred: Thanks Fred. Did not know that. I have been used to using srand all the time.
You should probably delete this answer as it is wrong and - even worse - it appears correct and indeed is correct in some implementations, but not all, making this advice very dangerous.
As @Fred explained above what random_shuffle uses to generate random number is implementation defined. This means that on your implementation it uses rand() (and hence srand() works) but on mine it can use something totally different, meaning that on my implementation even with srand every time I run the program I will get the same results.
@Code: like we discussed it doesn't work in all implementations. The fact that you can supply your own number generation is not mentioned in your answer and unrelated to this discussion in any case. I feel like we're going in circles :S
A
Apollys supports Monica

It can be even simpler, seeding can be avoided entirely:

#include <algorithm>
#include <random>

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

This will produce a new shuffle each time the program is run. I also like this approach due to the simplicity of the code.

This works because all we need for std::shuffle is a UniformRandomBitGenerator, whose requirements std::random_device meets.

Note: if shuffling repeatedly, it may be better to store the random_device in a local variable:

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

What does this add that wasn't already part of the accepted answer from 8 years ago?
All you have to do is read the answer to find out... There's not much more to be said that hasn't already been very clearly explained above.
The old accepted answer might be more in-depth. However, this is precisely the single-line point-and-shot answer I would expect when googling for such a simple question without much ado. +1
This is wrong. random_device is designed to be called only once to seed PRNGs, not to be called over and over again (which may exhaust the underlying entropy quickly and cause it switch to a sub-optimal generation scheme)
That may be an important caveat to add, but it's very far from making this "wrong" as you so dramatically accuse.
m
madx

If you are using boost you could use this class (debug_mode is set to false, if you want that the randomizing could be predictable beetween execution you have to set it to 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_));
    }
};

Than you can test it with this 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;
}

Why are you using time to seed the generator instead of std::random_device?
O
Ocezo

Depending of the standard you have to follow (C++11/C++14/C++17) this "cppreference" page provides pretty good examples: https://en.cppreference.com/w/cpp/algorithm/random_shuffle.