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?

Cage

You for got to seed rand srand. – Shoa

std :: srand(std :: time(NULL)) – Hypocorism

Answer 1

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.

Shoa

@Chin: note that you should seed the generator once when the program starts and never again. – Bushwa

is there any difference between time(0) and time(NULL)? – Cage

Good point I assumed the code he posted was part of int main(). I included the excerpt from the link.. – Shoa

@Chin, NULL should be used with pointers, and has been superseded by nullptr. – Alexandro

@Cage There are three ways of writing a null pointer in C++: Using the old NULL (inherited from C), using 0 (the old C++ way) and using the new C++11 keyword nullptr. – Campbellite

I think cstdlib is not needed, but ctime instead, otherwise I get a "identifier time is undefined" – Cage

srand() requires cstdlib. Something else might be pulling it in for you, but you should included it anyway. – Forestaysail

random_shuffle() isn't actually specified to use rand() and so srand() may not have any impact. If you want to be sure, you should use one of the C++11 forms, random_shuffle(b, e, RNG) or shuffle(b, e, uRNG) – Twirl

That is correct, it just so happens that rand is often used. – Shoa

You have to #include <ctime> for std::time(). – Kerosene

Answer 2

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

Kerosene

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.

Inventor