Producing permutations, part seven

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

6 thoughts on “Producing permutations, part seven

  1. 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.

  2. 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”?

  3. Pingback: .net - ¿Cómo puedo generar un azar BigInteger dentro de un cierto rango?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s