Storing data in a deck of cards

Question

This question has been bugging me for a while now. There are approximately 8e67 unique permutations of a standard, 52 card deck. This theoretically equates to just slightly more than 225 bits of data ($\log_2(52!)$).

So the question is; is it possible to design an algorithm to convert between a sequence of 52 cards and a 226 bit string such that every unique string is a unique number?

Ideally, the algorithm would be reversible. One should be able to go from a deck of cards to a string of data, or from a string of data to a deck of cards.

I wonder, also, if such an algorithm could run in linear time.

Something I thought of, though wasn't able to do anything with, was the notion that all of the cards in order would represent the lowest number, and all of the cards in reverse order would represent the highest number.

1,2,3 -> 0
3,2,1 -> 5

This did help a bit, because it meant I could do things like reverse the 1 and 2 to make the number one. 2,1,3 -> 1 And it wouldn't matter how many numbers come after a reversed sequence. 3,2,1 -> 5 as well as 3,2,1,4,5,6,7,8 -> 5

It gave me some rules as well. Given any two permutations that are nearly identical but differ only by two cards, the set with the higher card first would resolve to a higher number. I.E. 1,2,3,4,5 < 1,2,4,3,5 and 2,1,3 < 3,1,2

For two cards, the table is easy

1,2 -> 0
2,1 -> 1

For three cards there are sequences that obviously fall in line.

1,2,3 -> 0
2,1,3 -> 1
3,2,1 -> 5

Answer 1

After a few days of thinking about this, I figured it out. I was on the right track about the reverse order thing, but I was letting it hold me back, especially when trying to make it fit into linear time. What I should have been thinking about was how the movement of these cards could create a recursive sequence.

I think the easiest way to demonstrate what I've come up with is with some examples.

First, a deck of 1 card. There is only one possibility, so the i/o of the function would look like this: 1 -> 0.

This, of course, is still identical to 1,2,3,4,5,6,7... -> 0. As long as the sequence is in order, the output is zero.

So now we add a second card. With two cards there are two possible permutations of our deck. 1,2 -> 0 and 2,1 -> 1

What is significant about the second set is not that the sequence is reversed, but that the two moved to the left one space. The way we calculate the output of this iteration is we get the factorial of the number below the highest digit, and multiply that by how many spaces it is to the left. In our case, for 2,1, that's $1! * 1$.

Here's all of the possible sequences for a deck of three cards:

1,2,3 -> 0
2,1,3 -> 1
1,3,2 -> 2
2,3,1 -> 3
3,1,2 -> 4
3,2,1 -> 5

Notice that the ordering of cards 1 and 2 repeat in a pattern as the 3 card moves its way to the beginning.

Here's an even more verbose example showing 4 cards:

// The three card sequence, but there's a 4 at the end.
1,2,3,4 -> 0
2,1,3,4 -> 1
1,3,2,4 -> 2
2,3,1,4 -> 3
3,1,2,4 -> 4
3,2,1,4 -> 5

// If you imagine there is no 4 card, the sequence is just repeating
1,2,4,3 -> 6
2,1,4,3 -> 7
1,3,4,2 -> 8
2,3,4,1 -> 9
3,1,4,2 -> 10
3,2,4,1 -> 11

// The numbers increase as the 4 moves to the left
1,4,2,3 -> 12
2,4,1,3 -> 13
1,4,3,2 -> 14
2,4,3,1 -> 15
3,4,1,2 -> 16
3,4,2,1 -> 17

// The 4 reaches the left side
// The last permutation is all cards in reverse order
4,1,2,3 -> 18
4,2,1,3 -> 19
4,1,3,2 -> 20
4,2,3,1 -> 21
4,3,1,2 -> 22
4,3,2,1 -> 23

Decoding

Let's calculate the sequence 3,4,1,2 which we know is 16.

$T$ = accumulating total. $n$ = card number. $d$ = delta, or position from the right.

1. Find the position of the 4 card from the right. In this case it's moved by 2. So, $d = 2$

2. Add to $T$ such that $T' = T + d * (n-1)!$

3. Remove the 4 card from the list

4. Repeat until there is only one card left

T = 0
[3,4,1,2] -> n = 4, d = 2 -> 2 * 3! -> T' = T + 12
[3,1,2]   -> n = 3, d = 2 -> 2 * 2! -> T' = T + 4
[2,1]     -> n = 2, d = 0 -> 0 * 1! -> T' = T + 0
[1]       -> T = 16

Here's some pseudocode:

T = 0
for n in reverse(range(2, len(array) + 1)):
    p = array.index(n)
    d = n - p - 1
    T = T + d * factorial(n - 1)
    array.pop(p)

Encoding

I have not created an encoder yet, though I imagine it would be similar to the algorithm above, but in reverse. I will update this if or when I create one.

Answer 2

You're basically looking at Lehmer code, with a little bit of the factorial number system (aka factoradic) included. Here are the rough algorithms for going in each direction:

Mapping a permutation to an integer

Input: n, an integer
       a = [a_1, a_2, ... a_n] where a_i is the value of the item in the i-th position, minus 1 (so each a_i is a distinct value between 0 and n-1)

Output: N, an integer between 0 and n!-1

N = 0
for each i in 1 to n do
    N := N + (n-i)!*a_i
    for each j in i+1 to n do
        if a_j > a_i then a_j := a_j - 1

Mapping an integer to a permutation

Input: n, an integer
       N, a number between 0 and n!-1

Output: a = [a_1, a_2, ..., a_n] as described above

source := [0, .., n-1]
a := []

for each i in 1 to n do
     next := floor(N / (i-1)!)
     a[i] := source[next]
     source := source[-next] # i.e. remove the chosen element from the source set
     N := N - next

Please note that the above code comes completely unproven. Also, note that the first code is O(n^2), but the second is O(n) assuming you can update source in linear time.