Minimum number of bits required to store the order of a deck of cards

Question

Assume I have a shuffled deck of cards (52 cards, all normal, no jokers) I'd like to record the order in my computer in such a way that the ordering requires the least bits (I'm not counting look up tables ect as part of the deal, just the ordering itself.

For example, I could record a set of strings in memory:

"eight of clubs", "nine of dimonds"

but that's obviously silly, more sensibly I could give each card an (unsigned) integer and just record that...

17, 9, 51, 33...

which is much better (and I think would be around 6 bits per number times 53 numbers so around 318 bits), but probably still not ideal.. for a start I wouldn't have to record the last card, taking me to 312 bits, and if I know that the penultimate card is one of two choices then I could drop to 306 bits plus one bit that was true if the last card was the highest value of the two remaining cards and false otherwise....

I could do some other flips and tricks, but I also suspect that this is a branch of maths were there is an elegant answer...

Answer 1

There are $52!$ possible ordering of the 52 cards. Each bit can store 2 value, so you need to find the smallest $n$ for which $2^n\geq52!$, $n\geq log_2(52!)$, that is $226$.

The algorithm for rebuild the ordering from the number is the one suggested by Ross Millikan.

Answer 2

As carlop says, you can store the order number in 226 bits. Then to find the order of the cards, divide the order number by 51!. The quotient is the card number of the first card and the remainder is the order number of the remaining 51 cards.

Added: If you just store a card number (0-51) for each position, it takes 6 bits per card, for a total of 312 bits. It costs less than 100 bits and is easier to unpack. The preceding approach assumes you keep track of which cards are used, so after you have done 20 cards, you can go down to 5 bits, after 36 you can go to 4 bits, etc. In this case you use 0 for the last card, 1 for the next to last, 2 for the next two, etc 0+1+2*2+3*4+4*8+5*16+6*20=249 bits. This is not much of an increase over the best possible. The increase comes because storing the number of the ordering takes advantage of the wasted data in using 6 bits to pick one of 40, for example.

Answer 3

As the other answers point out, you can code the permutations in several ways, but you'll need at least 226 bits (in average). To read about concrete encoding schemes, you can start here