C++ random_shuffle() how does it work?

Question

I have a Deck vector with 52 Card, and I want to shuffle it.

vector<Card^> cards;

So I used this:

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

The problem was that it gave me the same result every time, so I used srand to randomize it:

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

This was still not truly random. When I started dealing cards, it was the same as in the last run. For example: "1. deal: A,6,3,2,K; 2. deal: Q,8,4,J,2", and when I restarted the program I got exactly the same order of deals.

Then I used srand() and random_shuffle with its 3rd parameter:

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

Now it's working and always gives me different results on re-runs, but I don't know why it works this way. How do these functions work, what did I do here?

Answer 1

This answer required some investigation, looking at the C++ Standard Library headers in VC++ and looking at the C++ standard itself. I knew what the standard said, but I was curious about VC++ (including C++CLI) did their implementation.

First what does the standard say about std::random_shuffle . We can find that here. In particular it says:

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.

The bolded part is key. The standard says that the RNG can be implementation specific (so results across different compilers will vary). The standard suggests that std::rand is often used. But this isn't a requirement. So if an implementation doesn't use std::rand then it follows that it likely won't use std::srand for a starting seed. An interesting footnote is that the std::random_shuffle functions are deprecated as of C++14. However std::shuffle remains. My guess is that since std::shuffle requires you to provide a function object you are explicitly defining the behavior you want when generating random numbers, and that is an advantage over the older std::random_shuffle.

I took my VS2013 and looked at the C++ standard library headers and discovered that <algorithm> uses template class that uses a completely different pseudo-rng (PRNG) than std::rand with an index (seed) set to zero. Although this may vary in detail between different versions of VC++ (including C++/CLI) I think it is probable that most versions of VC++/CLI do something similar. This would explain why each time you run your application you get the same shuffled decks.

The option I would opt for if I am looking for a Pseudo RNG and I'm not doing cryptography is to use something well established like 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.

Luckily for us C++11 Standard Library (which I believe should work on VS2010 and later C++/CLI) includes a Mersenne Twister function object that can be used with std::shuffle Please see this C++ documentation for more details. The C++ Standard Library reference provided earlier actually contains code that does this:

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

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

The thing to note is that std::random_device produces non-deterministic (non repeatable) unsigned integers. We need non-deterministic data if we want to seed our Mersenne Twister (std::mt19937) PRNG with. This is similar in concept to seeding rand with srand(time(NULL)) (The latter not being an overly good source of randomness).

This looks all well and good but has one disadvantage when dealing with card shuffling. An unsigned integer on the Windows platform is 4 bytes (32 bits) and can store 2^32 values. This means there are only 4,294,967,296 possible starting points (seeds) therefore only that many ways to shuffle the deck. The problem is that there are 52! (52 factorial) ways to shuffle a standard 52 card deck. That happens to be 80658175170943878571660636856403766975289505440883277824000000000000 ways, which is far bigger than the number of unique ways we can get from setting a 32-bit seed.

Thankfully, Mersenne Twister can accept seeds between 0 and 2^19937-1. 52! is a big number but all combinations can be represented with a seed of 226 bits (or ~29 bytes). The Standard Library allow std::mt19937 to accept a seed up to 2^19937-1 (~624 bytes of data) if we so choose. But since we need only 226 bits the following code would allow us to create 29 bytes of non-deterministic data to be used as a suitable seed for 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);  

Then all you need to do is call shuffle with code like:

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

On Windows VC++/CLI you will get a warning that you'll want to suppress with the code above. So at the top of the file (before other includes) you can add this:

#define _SCL_SECURE_NO_WARNINGS 1