# 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?

source to share

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 thestd :: randfunction 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
```

source to share