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 (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.
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
Fabulous adventures in coding 
The number of permutations thing was something I brought up way back in the first or second article as well, though I stated the problem as one of indexing them.
Anyway I really have to thank you a ton for putting these out there. I found an application you may not have considered which was a massive help.
Me and a friend had to tear apart a deck and rebuild it. The top board is really expensive composite material that we had to be careful to save. However it’s cut into a few lengths: 12ft, 9ft, 5.4ft, 3ft, etc. What your permutation concept allowed me to put together is to punch in the lengths and run the permutations through a sort, popping combinations that add up to our target deck width.
First day we began to put the top board onto the new deck frame it was taking up to 10 minutes each to figure out in our heads which combinations would work. Now however we just type in our target and voila a list sorted of combinations we can use.
Excellent! For your future reference, there are many famous problems that are similar to your board-sawing optimization problem. See http://en.wikipedia.org/wiki/Cutting_stock_problem, http://en.wikipedia.org/wiki/Knapsack_problem and http://en.wikipedia.org/wiki/Packing_problem for some interesting reading.
Also, I am embarking upon the same venture: building a deck out of expensive AZEK board. I might ask you for your source code. 🙂
A couple of corrections. You refer to “Math.Random” several times. I think you meant “System.Random”.
Also, you said, “There are 52 x 51 x 50 x 49 x 48 = about 2^28…” Did you mean “2^228”?
Ahhh … I re-read the “2^28” part. Makes sense now. Need caffeine.
Pingback: .net - ¿Cómo puedo generar un azar BigInteger dentro de un cierto rango?