will this output a random shuffle a million times? rand() c++

Question

i'm attempting to run a million simulations of a card game to return a percentage "casino house edge."

my understanding of the rand() function is not clear enough to know whether this will generate a new shuffle every time or if it has a limit. in other words, at some point into the million games, will the same patterns of shuffles emerge?

  srand(time(NULL));

for (int games=0;games<iGames;games++){

                  ///shuffle///
for (int i=0; i<(iUserDeckSize-1); i++) {
    int r = i + (rand() % (iUserDeckSize-i)); // Random remaining position.
    card temp = cards[i]; cards[i] = cards[r]; cards[r] = temp;
}

// rest of card game code goes here
}

There should be a shuffle in `` if my memory is right... Here: http://www.cplusplus.com/reference/algorithm/random_shuffle/ — nhahtdh, Dec 24 '12 at 05:49
`rand()` is a pseudo-random number generator. This means that *eventually* (and likely a very-large-don't-care-about eventually) there will be a repeating sequence. However, since this restart may happen "not always at the start of a shuffle" then it seems like there could be *more* shuffle permutations than the cycle length of the employed PRNG. — , Dec 24 '12 at 05:51
I believe it's implementation specific, see here for instance http://stackoverflow.com/questions/1026327/what-common-algorithms-are-used-for-cs-rand. But I'd be astounded if practical implementations began repeating that quickly, I would have thought at least you'd get into the billions allowed by an int32. — PeterJ, Dec 24 '12 at 05:53

score 1 · Answer 1 · edited May 23 '17 at 11:48

1

I believe it's implementation specific, see here for instance What common algorithms are used for C's rand()?. But I'd be astounded if practical implementations began repeating that quickly, I would have thought you'd at least get into the billions allowed by an int32.

edited May 23 '17 at 11:48

Community

1
1

answered Dec 25 '12 at 00:10

PeterJ

3,705
28
51
71

Maciej Piechotka · Accepted Answer · 2012-12-25T00:39:01.997

No for 2 reasons (one you thought about and one not-so-obvious).

The algorithm you are using is wrong. Setting aside worrisome -1 (the last element will not be shuffled at all) you have n^n possible runs (space of received random numbers) while there is n! possible shuffles. In general n! is not a factor of n^n hence you have biased output (i.e. some outcomes will occur more often then others). I would recommend either implement the Knuth-Tares shuffle or use already implemented algorithm like random_shuffle from <algorithm>.

That said - you need to have the PRNG which have at least n! states. Depending on the deck size rand() may not be enough - it typically have ~48 bits while standard 52-card deck have ~225 bits of state (log2(52!)) - in other words there is no chance of hitting some sequences (it might not be a problem but overhead of better PRNG is negligible). I would look on boost random as it have several good PRNG implementations and at least one would probably be sufficiently good (say mt11213b for 52-card example).

will this output a random shuffle a million times? rand() c++

2 Answers2