如何对 std::vector 进行洗牌？

Question

我正在寻找一种通用、可重复使用的方法来对C++中的std::vector进行洗牌。这是我的当前方法，但我认为它并不是非常高效，因为它需要一个中间数组，并且需要知道项目类型（在此示例中为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

---

不对。查一下 Fisher-Yates 算法... - Mitch Wheat

尽量避免使用 rand()，有更好的随机数生成器API可用（例如Boost.Random或0x <random>）。 - Cat Plus Plus

链接：https://dev59.com/6HVC5IYBdhLWcg3w51ry - Sardathrion - against SE abuse

Answer 1

从C++11开始，你应该优先考虑：

#include <algorithm>
#include <random>

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

在 Coliru 上的实时示例

如果您打算每次生成不同的排列，请确保在多次调用std::shuffle时重复使用相同的rng实例！

此外，如果您希望您的程序在每次运行时创建不同顺序的洗牌序列，可以使用std::random_device的输出种植随机引擎的构造函数：

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

对于 C++98，您可以使用：

#include <algorithm>

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

- user703016

---

你也可以将自定义的随机数生成器作为 std::random_shuffle 的第三个参数传入。 - Alexandre C.

请注意，这可能会导致程序每次运行时都产生相同的结果。如果出现这种问题，您可以将自定义随机数生成器（可以从外部源进行种子设置）作为 std::random_shuffle 的附加参数添加进去。 - Mankarse

@Gob00st: 它将为程序的每个实例生成相同的结果，而不是每次调用random_shuffle。这种行为是正常且预期的。 - user703016

@ParkYoung-Bae 谢谢，我刚刚发现这个网址（http://www.cplusplus.com/reference/algorithm/random_shuffle/）。当SO的答案没有包含include信息时，它真的很不方便，因为它们排在谷歌搜索结果的前面。 - Tomáš Zato

我会尽力为您翻译，以下是需要翻译的内容：“我认为你应该在回答中加入如何对向量进行随机化的方法。很多人（比如我）之所以来到这里，是因为他们在谷歌搜索“c++，向量随机洗牌”。” 建议译文：我认为你应该在回答中加入如何对向量进行种子化操作的方法。很多人（包括我自己）通过谷歌搜索 "C++ shuffle vector" 找到这里。 - Jonny

Answer 2

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

---

一个糟糕的例子，复制自http://www.cplusplus.com/reference/algorithm/shuffle/。如何进行另一次shuffle调用？ - miracle173

@miracle173 示例改进 - Mehmet Fide

为什么在生成随机数种子时要使用系统时钟的奇怪方法，而不是直接使用“std::random_device”？ - Chuck Walbourn

Answer 3

除了 @Cicada 提出的建议外，你应该先进行种子操作。

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

根据@FredLarson的评论： 此版本random_shuffle（）的随机源是由实现定义的，因此它可能根本不使用rand（）。然后srand（）将没有任何效果。 所以你的结果可能会有所不同。

- user195488

---

实际上，这个版本的 random_shuffle() 的随机源是由实现定义的，因此它可能根本不使用 rand()，这时 srand() 就没有作用了。我以前遇到过这种情况。 - Fred Larson

@Fred：谢谢Fred。我不知道这个。我一直习惯使用srand。 - user195488

由于这个答案是错误的，而且更糟糕的是，在某些实现中它看起来是正确的，但并非所有实现都是如此，因此建议您删除它。请注意，这些建议非常危险。 - Andreas Bonini

正如@Fred在上面所解释的那样，random_shuffle用于生成随机数的方法是由实现定义的。这意味着在您的实现中它使用了rand()（因此srand()有效），但在我的实现中它可能使用完全不同的东西，这意味着在我的实现中，即使使用srand，每次运行程序我都将得到相同的结果。 - Andreas Bonini

@代码：就像我们讨论的那样，它在所有实现中都不起作用。你可以提供自己的数字生成，这一事实并未在你的答案中提到，而且与本次讨论无关。我觉得我们正在打转 :S - Andreas Bonini

Answer 4

甚至可以更简单，完全可以避免使用种子：

#include <algorithm>
#include <random>

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

每次运行程序都会产生一个新的洗牌结果。我喜欢这种方法是因为代码简单易懂。

这种方法可行的原因是我们只需要使用std::shuffle，而它所需要的UniformRandomBitGenerator已被std::random_device满足。

注意：如果需要重复洗牌，最好将random_device存储在本地变量中：

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

- Apollys supports Monica

---

这个有什么新增的内容，而之前已经在8年前的答案中被接受了呢？ - ChrisMM

你所要做的就是阅读答案，就能找到答案了...除了以上已经非常清楚地解释过的内容，没有更多需要说的了。 - Apollys supports Monica

已经接受的答案已经使用了shuffle，并建议使用random_device... - ChrisMM

旧的被接受的答案可能更加深入。然而，这正是我期望的单行点射式答案，当我在谷歌上搜索这样一个简单问题时，不需要太多的麻烦。+1 - Ichthyo

这是错误的。random_device 的设计初衷是仅被调用一次以种子 PRNG，而不是反复调用（这可能会迅速耗尽底层熵并导致其切换到次优的生成方案）。 - L. F.

这可能是需要添加的重要说明，但与您如此激烈指责的“错误”相去甚远。 - Apollys supports Monica

Answer 5

如果您正在使用boost，您可以使用此类（debug_mode设置为false，如果您希望随机化在执行之间可预测，您必须将其设置为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_));
    }
};

您可以使用以下代码进行测试：

#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

---

你为什么要使用时间来种子化生成器，而不是使用“std::random_device”？ - Chuck Walbourn

Boost随机洗牌是否比普通洗牌更好？ - Moin ud-din

Answer 6

根据你需要遵循的标准（C++11/C++14/C++17），这个“cppreference”页面提供了相当不错的示例：https://en.cppreference.com/w/cpp/algorithm/random_shuffle。

- Ocezo