Last time on FAIC I generated a “random” permutation of a deck of cards and gave you the first five cards, and challenged you to determine what the next five cards were. David Poeschl[1. Of the Roslyn team!] was the first to get a possible order and, with the additional hint that the sixth card was the three of hearts, Joel Rondeau found the correct solution, which is below. Both used brute-force algorithms.
The problem with my algorithm, as David points out in the comments, is that there are 52! possible orderings of a deck, which is approximately 2226, but there are only 232 possible “seeds” to the pseudo-random number generate that is
Math.Random, and therefore only a tiny fraction of the decks can possibly be generated. In fact, the situation is far worse than that; when no seed is given, the class defaults to using the absolute value of
Environment.TickCount which measures the number of milliseconds since the machine was turned on. However, this value is only updated approximately 60 times a second. The upshot of this is:
- Because the absolute value is taken, the actual seed is only drawn from 231 possible values.
- Since a lot of people boot their machines when they need them rather than keeping them on all the time, the seed is typically much less than the number of milliseconds in a day.
- If Random is seeded twice and you manage to work out one of the seeds, you might be able to cut down the problem of figuring out the other by a factor of 60 or so — not that it matters; as we’ve seen, brute-forcing is fast.
There are 52 x 51 x 50 x 49 x 48 = about 228 possible first five cards of a deck, and 231 possible seeds. That means that on average there will be only 23 decks that can possibly be generated by this algorithm that start with those five cards, out of the actual 2197 decks that could start with those five cards! And when given a sixth card, it is almost always going to be possible to find the unique deck that can be generated using this algorithm.
If you’re going to be shuffling a deck of cards by choosing a random permutation and there is a need for actual unpredictability then you should use a random or pseudo-random number generator that has at least 226 bits of “entropy” in the seed. The
RandomNumberGenerator class is suitable for this purpose,
Math.Random is not.
Next time on FAIC: I’ve been asked to write a series of articles for another site and they’ll take me a bit to work out, so I’ll probably skip the next couple of episodes of FAIC. More bulletins as events warrant.
39: Ace of Clubs 11: Queen of Spades 29: Four of Diamonds 5: Six of Spades 20: Eight of Hearts 15: Trey of Hearts 3: Four of Spades 16: Four of Hearts 33: Eight of Diamonds 43: Five of Clubs 49: Jack of Clubs 1: Deuce of Spades 22: Ten of Hearts 27: Deuce of Diamonds 25: King of Hearts 2: Trey of Spades 44: Six of Clubs 6: Seven of Spades 21: Nine of Hearts 17: Five of Hearts 35: Ten of Diamonds 12: King of Spades 48: Ten of Clubs 4: Five of Spades 41: Trey of Clubs 42: Four of Clubs 51: King of Clubs 36: Jack of Diamonds 7: Eight of Spades 28: Trey of Diamonds 18: Six of Hearts 0: Ace of Spades 13: Ace of Hearts 14: Deuce of Hearts 10: Jack of Spades 9: Ten of Spades 24: Queen of Hearts 50: Queen of Clubs 19: Seven of Hearts 47: Nine of Clubs 37: Queen of Diamonds 34: Nine of Diamonds 40: Deuce of Clubs 45: Seven of Clubs 23: Jack of Hearts 31: Six of Diamonds 32: Seven of Diamonds 30: Five of Diamonds 46: Eight of Clubs 8: Nine of Spades 38: King of Diamonds 26: Ace of Diamonds