random - C++ random_shuffle() 它是如何工作的？

Question

我有一个包含 52 张牌的牌组向量，我想对其进行洗牌。

vector<Card^> cards;

所以我用了这个:

random_shuffle(cards.begin(), cards.end());

问题是它每次都给我相同的结果，所以我使用 srand 对其进行随机化:

srand(unsigned(time(NULL))); 
random_shuffle(cards.begin(),cards.end());

这仍然不是真正随机的。当我开始发牌时，情况与上次相同。例如:“1. 交易:A,6,3,2,K；2. 交易:Q,8,4,J,2”，当我重新启动程序时，我得到了完全相同的交易顺序。

然后我使用了 srand() 和 random_shuffle 及其第三个参数:

 int myrandom (int i) {
    return std::rand()%i; 
 }
 srand(unsigned(time(NULL))); 
 random_shuffle(cards.begin(),cards.end(), myrandom);

现在它正在工作，并且在重新运行时总是给我不同的结果，但我不知道为什么它会这样工作。这些功能是如何工作的，我在这里做了什么？

Answer 1

这个答案需要一些调查，查看 VC++ 中的 C++ 标准库 header 并查看 C++ 标准本身。我知道标准的内容，但我很好奇 VC++(包括 C++CLI)是否实现了它们。

首先，标准对 std::random_shuffle 有何规定？ 。我们可以发现here 。它特别指出:

Reorders the elements in the given range [first, last) such that each possible permutation of those elements has equal probability of appearance.

1) The random number generator is implementation-defined, but the function std::rand is often used.

粗体部分是关键。该标准规定 RNG 可以是特定于实现的(因此不同编译器的结果会有所不同)。标准表明 std::rand 经常使用。但这不是一个要求。因此，如果实现不使用 std::rand那么它可能不会使用 std::srand作为起始种子。一个有趣的脚注是 std::random_shuffle从 C++14 开始，函数已被弃用。然而std::shuffle遗迹。我的猜测是，自从 std::shuffle要求您提供一个函数对象，您在生成随机数时显式定义所需的行为，这比旧的 std::random_shuffle 有优势。 .

我拿着我的VS2013查看了C++标准库头文件，发现<algorithm>使用与 std::rand 完全不同的伪 rng (PRNG) 的模板类索引(种子)设置为零。尽管不同版本的 VC++(包括 C++/CLI)之间的细节可能有所不同，但我认为大多数版本的 VC++/CLI 可能都会做类似的事情。这可以解释为什么每次运行应用程序时都会得到相同的洗牌牌。

如果我正在寻找伪 RNG 并且我不做密码学，我会选择的选项是使用像 Mersenne Twister 这样成熟的东西。 :

Advantages The commonly-used version of Mersenne Twister, MT19937, which produces a sequence of 32-bit integers, has the following desirable properties:

It has a very long period of 2^19937 − 1. While a long period is not a guarantee of quality in a random number generator, short periods (such as the 2^32 common in many older software packages) can be problematic.

It is k-distributed to 32-bit accuracy for every 1 ≤ k ≤ 623 (see definition below).

It passes numerous tests for statistical randomness, including the Diehard tests.

幸运的是，C++11 标准库(我相信它应该适用于 VS2010 和更高版本的 C++/CLI)包含一个可与 std::shuffle 一起使用的 Mersenne Twister 函数对象。请看这个C++ documentation更多细节。前面提供的 C++ 标准库引用实际上包含执行此操作的代码:

std::random_device rd;
std::mt19937 g(rd());

std::shuffle(v.begin(), v.end(), g);

需要注意的是std::random_device产生不确定的(不可重复的)无符号整数。如果我们想要为 Mersenne Twister ( std::mt19937 ) PRNG 播种，我们需要非确定性数据。这在概念上与播种 rand 类似。与 srand(time(NULL)) (后者并不是一个很好的随机性来源)。

这看起来一切都很好，但在处理洗牌时有一个缺点。 Windows 平台上的无符号整数为 4 个字节(32 位)，可以存储 2^32 个值。这意味着只有 4,294,967,296 个可能的起始点(种子)，因此洗牌的方法也只有这么多。问题是有52个! (52 阶乘)洗标准 52 张牌的方法。这恰好是 80658175170943878571660636856403766975289505440883277824000000000000 种方式，这远远大于我们通过设置 32 位种子可以获得的独特方式的数量。

值得庆幸的是，Mersenne Twister 可以接受 0 到 2^19937-1 之间的种子。 52!是一个很大的数字，但所有组合都可以用 226 位(或约 29 字节)的种子表示。标准库允许 std::mt19937如果我们选择的话，接受最多 2^19937-1(~624 字节数据)的种子。但由于我们只需要 226 位，以下代码将允许我们创建 29 字节的非确定性数据，用作 std::mt19937 的合适种子。 :

// rd is an array to hold 29 bytes of seed data which covers the 226 bits we need */
std::array<unsigned char, 29> seed_data; 
std::random_device rd;
std::generate_n(seed_data.data(), seed_data.size(), std::ref(rd));
std::seed_seq seq(std::begin(seed_data), std::end(seed_data));

// Set the seed  for Mersenne *using the 29 byte sequence*
std::mt19937 g(seq);  

然后您需要做的就是使用如下代码调用 shuffle:

std::shuffle(cards.begin(),cards.end(), g);

在 Windows VC++/CLI 上，您将收到一条警告，您需要使用上面的代码来抑制该警告。因此，在文件顶部(在其他包含之前)您可以添加以下内容:

#define _SCL_SECURE_NO_WARNINGS 1