2
$\begingroup$

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

  • 0
    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.2012-04-21
  • 0
    @JacksonWalters could you elaborate how can we store permutations in cycle notation?2015-05-28
  • 0
    This may be totally off-topic but I felt like mentioning. I was playing with my deck of cards today and I noticed that (depending on the nature of your deck) there may be another 52 bits to add to the amount of information storable in a deck of cards: which way the cards face. You can tell from the edge of the cards which side is the "top". so we can rotate each card on the deck by 180 degrees to flip it as a bit. (still maintaining the cards all facing one side) Going further along this line of reasoning you may also rotate the facing direction of the cards, that adds another 51 bits I think.2017-01-08
  • 0
    @StevenLu: Yes, you can store another $2\cdot 52$ bits with face up/face down and head up/head down. There is a card trick where one magician is given five cards from a deck, keeps one and passes the other four to an accomplice. Without information from face up/face down the accomplice is able to name the card the magician kept. There are only $24$ orders of the four cards but $48$ others to choose from-where does the other bit come from?2017-01-08
  • 0
    @RossMillikan a bitta $S_3$ from the order of the first three cards!2017-11-24
  • 0
    @JpMcCarthy: I don't understand at all. The $24$ is from the order of all four, which includes the factor $6$ for the order of the first three.2017-11-24
  • 0
    @Ross Millikan A suit is repeated. Keep that as suit of last card. Consider A7 and A8. A+6=7 and 8+6=A. So pick two cards with same suit. Pick card closest to the other mod 13 for the first. This distance is between 1 and 6. Add using S3 to get the card of same suit in your hand. Voila!2017-11-24
  • 0
    @RossMillikan does the above help?2017-11-27
  • 0
    It is up that direction. The players have to agree which card will be kept out of each group of five that might be drawn.2017-11-27
  • 0
    @RossMillikan don't think so: they just agree the suit is the same as the first card, then the next three communicate what to add to the first card to get the last.2017-11-27

3 Answers 3

1

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

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.

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.