shuffle a deck of cards with one random number

the other day at work a guy was talking about a site that had a flawed method for shuffling a deck of cards. although it used a random number generator, the algorithm was flawed and it was possible in some cases to determine what cards your opponents had.

this got me thinking a bit about shuffling a deck of 52 cards. I was slightly surprised when I realized it is possible to shuffle a deck of 52 cards using only one number from a random number generator. it's not too difficult. it's something that could be a high school math problem. let's define the random number generator as a device that will produce a uniformly-distributed random number R in the range [0, 1).

I'll let it sit for a couple of days then post an answer

--

here's the solution.

there are 52! ways to arrange a deck of cards, about 10⁶⁸ or 80,658,175,170,943,900,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000. the important thing is that it is a finite set.

first enumerate the 52! permutations into a fixed ordered list L.

then using the random number R, let list_index = 1 + floor(R * 52!).

list_index will be an integer in the range [1, 52!]. the item in L at position list_index will be the sorted deck. qed.


so basically this is the same as arranging [0, 1) into 52! equal size partitions, and returning the piece that R lands in.


--

this solution also leads to another high school math/computer science problem. it would not be practical to create a list of 52! elements of size 52 bytes each.

here is the problem. describe a way to arrange L such at, given list_index, you can determine what the ordered 52 cards are for that list_index without having to do a lookup into L.

here is a sketch of a solution. arrange an original deck of cards in some specific fixed way such as { Ace of diamonds, King of diamonds, ... 3 of clubs, 2 of clubs }

now given any first card in the shuffled deck, there will be 51! ways to arrange the remaining cards. so if list_index is between [1, 51!] then the first card must be the Ace of diamonds, if between [51! + 1, 2 * 51!] then the first card is the King of diamonds, and so on

after determining the first card, remove that card from the original deck of cards, leaving the remaining 51 cards. now, use div and mod functions on list_index to similarly determine your "path" through list_index, removing the chosen card from your list at each stage. after 52 such iterations you will have the unique shuffled deck that corresponds to list_index.