C ++ random_shuffle () how does it work?

I have a 52-card deck vector and I want to shuffle it.

vector<Card^> cards;

      

So, I used this:

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

      

The problem was that it was giving me the same result every time, so I used srand

to randomize:

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

      

It still wasn't really random. When I started dealing cards, it was the same as in the last run. For example: "1. trade: A, 6,3,2, K; 2. trade: Q, 8,4, J, 2", and when I restarted the program, I got exactly the same order of trades.

Then I used srand()

and random_shuffle

with my third parameter:

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

      

Now it works and always gives me different results when I run it again, but I don't know why it works this way. How do these functions work, what have I done here?

+3


source to share


1 answer


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 had said, but I was curious that VC ++ (including C ++ CLI) followed their implementation.

First, what the standard says std::random_shuffle

. We can find it here . Specifically, he says:

Modifies the elements in the given range [first, last] so that every possible permutation of those elements has an equal probability of occurrence.

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

The bold part is key. The standard says that RNG can be implementation-specific (so results will vary for different compilers). The standard assumes that it std::rand

is used frequently. But this is not a requirement. Therefore, if an implementation does not use std::rand

, then it follows that it will not use std::srand

for seed. An interesting footnote is that functions are being std::random_shuffle

deprecated since C ++ 14. It std::shuffle

remains , however . My guess is that since it std::shuffle

requires you to provide a function object, you are explicitly defining the behavior you want when generating random numbers, and this is an advantage over the older ones std::random_shuffle

.

I took VS2013 and looked at the headers of the C ++ standard libraries and found that I was <algorithm>

using a templating class that uses a completely different pseudo-rng (PRNG) than std::rand

with the index (sample) set to zero. While this may vary in detail between different VC ++ versions (including C ++ / CLI), I think it is likely that most VC ++ / CLI versions do something similar. This explains why every time you launch the app you get the same shuffled decks.

The option I would choose if I am looking for a Pseudo RNG and I am not into crypto is to use something well established like the Mersenne Twister :

Benefits . The commonly used version of the 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 long periods are not a guarantee of quality in a random number generator, short periods (for example, 2 ^ 32 common to many older software packages) can be problematic.

     

It is k-allocated to 32-bit precision for each 1 ≤ k ≤ 623 (see definition below).

     

Passes many tests for statistical randomness, including Diehard tests.

Luckily for us, the C ++ 11 Standard Library (which I think should work on VS2010 and later C ++ / CLI) includes a Mersenne Twister function object that can be used with std::shuffle

See this C documentation ++ for more details. The C ++ Standard Library link above actually contains the code that does this:

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

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

      



It should be noted that it std::random_device

creates non-deterministic (non-repeatable) unsigned integers. We need non-deterministic data if we want to seed our Merrenne Twister ( std::mt19937

) PRNG. This is similar to the concept of rand

assisted seeding srand(time(NULL))

(the latter is not a very good source of randomness).

It looks good and good, but has one drawback when dealing with card shuffling. An unsigned integer on Windows platform is 4 bytes (32 bits) and can store 2 ^ 32 values. This means that there are only 4,294,967,296 possible starting points (seeds), so only for many ways to shuffle the deck. The problem is there are 52! (52 factorials) to shuffle a standard 52 deck of cards. It happens like this: 80658175170943878571660636856403766975289505440883277824000000000000 ways, which is much more than the number of unique ways that you can get a 32-bit seed.

Fortunately, the Mersenne Twister can accept seeds between 0 and 2 ^ 19937-1. 52! is a large number, but all combinations can be represented by a seed of 226 bits (or ~ 29 bytes). The standard library allows std::mt19937

up to 2 ^ 19937-1 seed (~ 624 bytes of data) to be accepted if we so desire. But since we only need 226 bits, the following code will allow us to create 29 bytes of non-deterministic data that will 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 you only need to shuffle the call with the code:

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

      

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

#define _SCL_SECURE_NO_WARNINGS 1

      

+7


source







All Articles