随机重排并不真正随机

Question

我正在使用random_shuffle函数对一个向量进行随机排序，代码如下：

#include <algorithm>
vector <Card> deck;
//some code to add cards to the deck here
random_shuffle ( deck.begin(), deck.end() );

运行时，卡片组的内容会被打乱，但是当我重新启动程序时，这个打乱的顺序被保留了下来。

我错过了什么吗？如何使它真正随机？

- Chin

---

你忘记了使用随机种子函数 srand。 - Joe

std :: srand(std :: time(NULL)) - Coding Mash

Answer 1

您需要首先使用 srand 种植伪随机数生成器。

#include <algorithm>
#include <cstdlib>

...

std::srand(std::time(0));

vector <Card> deck;
//some code to add cards to the deck here
random_shuffle ( deck.begin(), deck.end() );

以上链接中的注释：

通常情况下，伪随机数生成器应该在程序开始之前仅被种子化一次，即在调用rand()之前。不应该重复地进行种子化，或者每次您想要生成新的伪随机数集时重新进行种子化。

- Joe

---

time(0)和time(NULL)之间有什么区别吗？ - Chin

好的，我假设他发布的代码是int main()的一部分。我包括了链接中的摘录。 - Joe

@Chin 在C++中有三种写空指针的方式：使用旧的NULL（从C继承而来），使用0（旧的C++方式）和使用新的C++11关键字nullptr。 - Some programmer dude

random_shuffle()函数并没有明确使用rand()，因此srand()可能没有任何影响。如果你想要保证，你应该使用C++11中的其中一个形式：random_shuffle(b, e, RNG)或者shuffle(b, e, uRNG)。 - bames53

你必须 #include <ctime> 来使用 std::time()。 - maxschlepzig

Answer 2

在当前的C++（即C++11）中，您可以使用shuffle算法，它可以将一个伪随机数生成器（PRNG）对象（可以进行种子操作）作为第三个参数：

#include <iostream>
#include <random>
#include <algorithm>
#include <vector>
#include <string>
#include <ctime>
using namespace std;

int main(int argc, char **argv)
{
  vector<string> v;
  for (int i = 1; i<argc; ++i)
    v.push_back(argv[i]);
  mt19937 g(static_cast<uint32_t>(time(0)));
  shuffle(v.begin(), v.end(), g);
  for (auto &x : v)
    cout << x << ' ';
  cout << '\n';
}

（对于GCC 4.8.2，您需要通过g++ -std=c++11 -Wall -g shuffle.cc -o shuffle进行编译）。

在上面的示例中，PRNG使用当前系统时间作为种子。

对于C++11之前的编译器，STL中只有random_shuffle算法可用，但是即使使用该算法，您也可以选择向其提供一个数字生成器对象/函数。请注意，您不能仅仅将PRNG对象（如mtl19937）插入其中，因为它不提供operator()(U upper_bound)成员。

因此，您可以按照以下方式提供自己的适配器：

#include <iostream>
#include <random>
#include <algorithm>
#include <vector>
#include <string>
#include <ctime>
using namespace std;

struct Gen {
  mt19937 g;
  Gen()
   : g(static_cast<uint32_t>(time(0)))
  {
  }
  size_t operator()(size_t n)
  {
    std::uniform_int_distribution<size_t> d(0, n ? n-1 : 0);
    return d(g);
  }
};

int main(int argc, char **argv)
{
  vector<string> v;
  for (int i = 1; i<argc; ++i)
    v.push_back(argv[i]);
  random_shuffle(v.begin(), v.end(), Gen());
  for (vector<string>::const_iterator i = v.begin(); i != v.end(); ++i)
    cout << *i << ' ';
  cout << '\n';
}

- maxschlepzig

Answer 3

请将这行代码放置在页面中：

srand (time (0));

在您的代码中，在执行任何其他操作之前，例如在main()开始处，务必加入以下内容。

否则，将始终使用默认种子1，从而导致rand()及其它所有使用它的内容产生相同的序列。

- paxdiablo