random_shuffle not really random

Question

I'm using the random_shuffle on a vector like this:

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

When run, the content of the deck is mixed up, but this mixed-up order is kept when I restart the program.

Did I miss something? How can I make it truly random?

Answer 1

With current C++ (i.e. C++11) you can use the shuffle algorithm which can take a pseudo random number generator (PRNG) object (which you can seed) as third parameter:

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

(for GCC 4.8.2 you need to compile it via g++ -std=c++11 -Wall -g shuffle.cc -o shuffle)

In the above example, the PRNG is seeded with the current system time.

For pre-C++11 compilers you only have the random_shuffle algorithm in the STL - but even with that you can optionally specify a number generator object/function to it. Note that you can't just pluck in a PRNG object like mtl19937 into it (because it does not provide a operator()(U upper_bound) member).

Thus, you can supply your own adapter like this:

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

Answer 2

You need to seed the psuedo-random number generator first using 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() );

Note from link above:

Generally speaking, the pseudo-random number generator should only be seeded once, before any calls to rand(), and the start of the program. It should not be repeatedly seeded, or reseeded every time you wish to generate a new batch of pseudo-random numbers.

Answer 3

Place the line:

srand (time (0));

in your code before you do anything else, such as at the start of main().

Without that, the default seed of 1 will always be used, leading to identical sequences from rand() and anything that uses it.