Encode order of playing cards (data compression)

Question

Suppose we have a deck of cards, shuffled in a random configuration. We would like to find a $k$-bit code in which we explain the current order of the cards. This would be easy to do for $k=51 \cdot 6=306$, since we could encode our deck card-by-card, using $2$ bits for the coloring and $4$ bits for the number on each card.

We would like to optimalise this code. There exist $52!$ ways to arrange our deck, and so $k$ will have to be at least: $\lceil\log(52!)\rceil=226$. I'm asked to find a code for a $k$-value halfway between $306$ and $226$.

I understand that my code cannot work card-by-card, since there exist $52$ different cards and $\lceil \log(52)\rceil=6$. Therefore any card-by-card codation will lead to $k\geq306$.

Therefore I concluded my strategy should encode blocks of cards, another idea I had was to encode the colouring first and the numbers second.

Could anyone give me a hint about where to go from here?

Answer 1

Enumerate all the cards in the deck, say by value and suit in a simple manner, e.g. let diamonds be numbered 1 to 13, ace to king, then clubs 14 to 26, then hearts 27 to 39 and lastly spades 40 to 52.

As you encode cards one by one, decrease the value of every card above it. So the sequence $1,2,3,4$ means the ace, three, five and seven of diamonds, while the sequence $15,15,14, 15$ means the two, three, ace and then five of clubs.

In the beginning, use six bits for each number. After 20 cards, use five bits per card instead (since now the highest value among the cards is 32). Sixteen cards later, you can start using four bits per card. And so on.

In total, you use $$20\cdot6+16\cdot5+8\cdot4+4\cdot3+2\cdot2+1=249$$ bits, which is a bit better than what you were asked for (but of course not optimal)

Answer 2

According to Hoffman, the optimal lossless coding needs at least $H(s)$ bits on average for each code, where $h(s)$ is the entropy of the source $s$.

In your case there is no redundancy in the numbers that you want to encode. They are simly numbers starting from $1$ to $52!$. I could suggest using variable length coding. One needs to be careful about the code construction since it needs to be decodable and not all codes are decodable. It is explained in the wiki article how to do it.

Answer 3

Order the permutations of $\{1,2,\dots, 52\}$ in lexicographic order.

Encode the $r^{th}$ permutation in that list as $r$ (requiring no more than $226$ bits).

Find a way to get to and get back the permutation, given $r$.

Answer 4

To extend upon Arthur's solution:

There is a fair amount of space that goes unused between the highest available card and the end of the bit field. A fairly simple way to recover a bit of this is to encode two cards at a time. Using his same basic system I get 240 bits needed, only 14 bits above the theoretical minimum.