Go and get a deck of cards, shuffle it, and deal it out in the order you shuffled it. You may find this hard to believe, but it’s extraordinarily likely that no one ever has shuffled cards into the same order you just did.
You’ve probably heard this before, since it’s one of those quite interesting facts that does the rounds. But in case you haven’t, the reason is that the amount of different ways a 52 card deck can be ordered is astonishingly high. The number is so big it’s difficult to parse:
8065817517094387857166063685640376
6975289505440883277824000000000000
Yes that’s one number written across two lines. To get an idea how large this is, it’s significantly higher than the number of stars in the universe, the number of atoms in your body, and the number of seconds that have elapsed since the universe was created in the big bang.
I’ll take it one step further. Depending on who you ask, between 60 and 108 billion humans have ever lived, so we can use an average of 80 billion. Applying the Doomsday Argument to this average suggests that about 1.2 trillion humans will ever live (and there’s a blog post on that topic itself!).
So in the entirety of human history, if every human ever lived to an average of 70 years and spent every single second of their lives shuffling cards the entire output of humanity would only correspond to a miniature subset of the total possible permutations of a 52 card deck (3.3E-45% to be accurate).
So shuffle that deck, deal it out, and be impressed with a creation that only you have made.
This has an interesting relevance in the field of gambling, which requires randomized deals lest the player guess the card order. Using human dealers, decks can be shuffled in a way that makes them almost completely random (although studies have shown that a virgin deck must be shuffled anywhere from 4 to 7 times to eliminate the order inherent in the way it was packaged). But these days the vast majority of deck shuffling is done by computers, and it’s not trivial to make computers do things truly randomly.
The very first computer games that included card shuffling had extremely primitive random number generation and could only return limited unique decks. Random number generators require a ‘seed’ (ie. a start value upon which all others are based) and every sequence based on the same seed is identical. Games on the Atari 2600 and Intellivision (shown above) typically used hardware values or player input (such as the number of frame refreshes that occurred before the player pushed the start button) as seeds, but even then were limited to usually only a couple of hundred unique decks. Given enough time and effort therefore, you could know the entire order of cards based upon the first few dealt.
As time moved on the algorithms became more sophisticated, and so too did the random number generators, but even then it was possible to predict deck orders if you had enough information. In 1999 an online casino, in an attempt to demonstrate their games were not rigged, actually posted their RNG code online. Someone got it, worked out how they seeded (based on the clock time, as I did in my polycap simulation), and actually wrote their own code that was able to reproduce perfectly the shuffling of the games they were playing online.
So we get to today, where RNG’s use very creative ideas to seed themselves with truly random seeds (such as using code to convert video frames captured from random Youtube videos or 1 second of white noise from a radio into seeds). But there is still a problem in that the range of randomly generated numbers is still limited to about 4E38. In short, you can’t generate a number between 1 and 8.06E67, which means you cannot generate one number for each possible deck permutation.
There are ways around this (hint: using only a single coin you can generate two random values) but it makes the task of writing a deck shuffling simulator that can account for every possibly permutation non trivial.
I think.
So as a result of this thought experiment, Bernard’s going to do it! Here’s my design document:
1) Assign all 52 cards a random number
2) Sort them
3) Output shuffled deck
It’s trivial stuff, and should only take him a femtosecond or two to implement. But the true fun is in the testing! For what I’m really interested in is how many unique shuffles are completed before a repeat occurs. Therefore the output (deck order) will need to be saved as well as the time it takes for each shuffle to be completed. Plus, since 52! is insanely large (the world will end before his computer shuffles that many times) I’d say saving the first 15 cards + the time the shuffle occurred is sufficient to do some statistical analysis.
So there you go Bernard, there’s your challenge. Write the code, run it 1.3 trillion times*/**, save the first 15 cards in each deck and the time the shuffle was performed and then analyze it to see if any sequence repeated.
Let us know the results 🙂
* I’ll assume you have a modern Pentium running about 100k MIPS, and that this code requires maybe 1000 operations to execute (a big guess there; the sort could take many more), which means about 12000 seconds or 3.5 hours per experiment. However writing results will slow it down a lot I suspect. Good luck!
** A very rough mental calculation tells me this may be a file size in the order or 17Tb. I hope you have a lot of space! Even more luck to you sir!!
