Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
You might represent each permutation as an element of $S_{52}$ and store the permutations in cycle notion, which is particularly efficient. In most cases this would require less than 226 bits. –  Jackson Walters Apr 21 '12 at 17:13

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.