CareerCup

First off, let's choose a canonical ordering for the deck of cards known by both sender and receiver (for example, order first by suit hearts, spades, diamonds, clubs and then 2-10, J, Q, K, A within each suit) and then replace the standard symbols for each card with an integer between 1 and 52 denoting its order in this canonical order.


Theoretical Minimum
Our sequence or shuffle is an ordering of the integers between 1 and 52. There are 52! permutations of this sequence, and so the minimum number of bits required to send it is simply lg_2(52!), or sum_{n=1}^{52} lg_2(n), which is 225.58, meaning we necessarily need at least 226 bits to send our shuffle.

What's the best approach to do this?

Simple Approach

The simple approach would be to notice that we're trying to send 52 numbers between 1 and 52. We need a 6 bit number (2^6 = 64) to represent an arbitrary number between 1 and 52, so we can use 52 6 bit numbers, for a total of 312 bits. This is OK - compared to our theoretical minimum of 226, we're only using about 40% more space plus there's minimal coding/decoding involved.

Better Approach

We can notice that we don't always have 52 different options for each card - once we've sent a card, we can't send it again. So the last card in the shuffle, for example, will always be determined. It will be the card remaining after the first 51 cards we send. The second to last card has only 2 options, so we only need 1 bit to send that. So for each card we send the number of the card out of the ordered cards that we haven't already sent. If we have, for example, cards 5 and 42 remaining and we want to send card 5, we send the number 1. This gets us sum_{n=1}^{52} ceil(lg_2(n)) - it takes 6 bits for the first 20 cards (52 possibilities to 33 possibilities), 5 bits for the next 16 card (32 possibilities to 17 possibilities), etc. This gets us to a total of 249 bits. This is much better, but still 10% more than the theoretical minimum. Can we get closer?

Best Approach

Suppose we want to send three numbers x, y, z which we know will lie between 1 and 10, 11, 9, respectively. Each of x, y, z would take 4 bits (2^4 = 16) to send independently for a total of 12 bits. There are 990 possible combinations, so the theoretical minimum number of bits to send this triplet is lg_2(990)=9.95, or 10 bits.

Here's how to map sets of x,y,z to a unique number C for each combination. Let's treat C as a number with multiple bases - the lowest order digit will be of base 9, the next lowest of base 11, and the high order bit of base 10. Then we can use each digit to hold one of x, y, and z. We can calculate C as z + z_{max} (y + y_{max} (x)). Then we send C to our receiver in binary as a 10 bit number, and they decode it. The low order digit is z, which can be extracted by z = C % z_{max}. Then they shift C down a digit, so C_{adj} = (C - z) / z_{max}. And we repeat to pull off y, y = C_{adj} % y_{max}. And shift C down again to extract x, x = (C_adj - y) / y_{max}. Done! We've successfully sent our numbers in the theoretical minimum number of bits.

Sample Python encoding/decoding functions w/ an example:

def encode(nums, maxvals):
    C = 0
    for i in range(len(nums)):
        C *= maxvals[i]
        C += nums[i] - 1 #Numbers between 1 and maxval inclusive
    return C
    
def decode(C, maxvals):
    nums = []
    for i in range(len(maxvals))[::-1]:
        nums.append(C % maxvals[i] + 1) #Adding 1 to get between 1 and maxval
        C = (C - nums[-1] + 1) // maxvals[i]
    return nums[::-1]

nums = [9, 9, 9]
maxvals = [10, 11, 9]
C = encode(nums, maxvals)
print C

872

print decode(C, maxvals)

[9, 9, 9]

We can use the same trick with our card problem to send in the theoretical minimum --- in theory. In practice, this requires lots of arithmetic on very large integers (up to 52!) and so we might want to restrict ourself to compositing Cs to be less than, say, 32 bits. Even with this restriction, we can get to as low as 228 bits - less than 1% more than the minimum.

Clever Approach

The theoretical minimum we calculated only applies if all shuffles are equally probable. In the limit, my shuffling algorithm might have a bug in it where it doesn't shuffle at all, in which case 0 bits of data is sufficient to transmit my current shuffle. More practically, if I'm using a pseudo-random number generator to shuffle my deck, the number of distinct possible shuffles is limited by both the period of my random number generator and the number of possible seeds I'm using to shuffle with. If my PRNG has a period of 2^32, then there's only 2^32 possible shuffles - and if the receiver has a copy of my PRNG, they can generate the same shuffle if I send them my 32-bit seed.

Very interesting problem!
Optimally we need log2(52!) = 226 bits to send 52 cards.

I have other approach, as following:
Send first K cards.
Then, send 52-K cards recursively.

To send first K cards: there are K-permutations of 52 cards, which is P(K,52). This must take ceil(log2(P(K,52)) bits. After sending K cards, the receiver decodes these K cards, and now both sides know exactly which are 52-K cards remaining.

We can compute optimal K by dynamic programming (see my code for details).

An example for sending N = 6 cards:

Send first 1	cards, needs 3	bits for P(1,6) permutations, remains 5 cards.
Send next 3	cards, needs 6	bits for P(3,5) permutations, remains 2 cards.
Send next 1	cards, needs 1	bits for P(1,2) permutations, remains 1 cards.
Send last card, needs 0 bits (no information needed)

Total:   10 bits required for sending 6 cards.
Optimal: 10 bits required for sending 6 cards.

I can get a result of 227 bits for sending 52 cards, with following sequences, which is easy for encode/decode (less than 32bits each time):

Send first 1	cards, needs 6	bits for P(1,52) permutations, remains 51 cards.
Send next 1	cards, needs 6	bits for P(1,51) permutations, remains 50 cards.
Send next 3	cards, needs 17	bits for P(3,50) permutations, remains 47 cards.
Send next 6	cards, needs 33	bits for P(6,47) permutations, remains 41 cards.
Send next 3	cards, needs 16	bits for P(3,41) permutations, remains 38 cards.
Send next 6	cards, needs 31	bits for P(6,38) permutations, remains 32 cards.
Send next 1	cards, needs 5	bits for P(1,32) permutations, remains 31 cards.
Send next 6	cards, needs 29	bits for P(6,31) permutations, remains 25 cards.
Send next 6	cards, needs 27	bits for P(6,25) permutations, remains 19 cards.
Send next 7	cards, needs 28	bits for P(7,19) permutations, remains 12 cards.
Send next 7	cards, needs 22	bits for P(7,12) permutations, remains 5 cards.
Send next 5	cards, needs 7	bits for P(5,5) permutations, remains 0 cards.
Send last card, needs 0 bits (no information needed)

Total:   227 bits required for sending 52 cards.
Optimal: 226 bits required for sending 52 cards.

One of optimal sequences is (but quite hard to encode/decode):

Send first 8	cards, needs 45	bits for P(8,52) permutations, remains 44 cards.
Send next 10	cards, needs 53	bits for P(10,44) permutations, remains 34 cards.
Send next 5	cards, needs 25	bits for P(5,34) permutations, remains 29 cards.
Send next 17	cards, needs 74	bits for P(17,29) permutations, remains 12 cards.
Send next 12	cards, needs 29	bits for P(12,12) permutations, remains 0 cards.
Send last card, needs 0 bits (no information needed)

Total:   226 bits required for sending 52 cards.
Optimal: 226 bits required for sending 52 cards.

Following program gives above result:

#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

const int NMax = 100;

double log2_Of_Factorial_N(int N){ //log2(N!)
    double res = 0;
    for(int i = N; i>1;i--)
        res += log2(i);

    return res;
};

double log2_Of_K_Permutation_Of_N(int K, int N){ // log2(P(K,N))
    return log2_Of_Factorial_N(N) - log2_Of_Factorial_N(N-K);
};

int memo[NMax] = {0};
int best[NMax] = {0};

void init(){
    best[3] = 3;
    best[2] = 1;
    best[1] = 1;
}

int send(int N, int MaxLen){    //recursive DP with memoization
    if (N<=1) return 0;
    if (N<=2) return 1;
    if (N<=3) return 3;

    if (memo[N]>0) return memo[N];

    int min = 1000000;
    int Kmin = -1;
    int nBits; // number of bits needed;

    for(int K = 1; K<=MaxLen; K++){
        nBits = ceil(log2_Of_K_Permutation_Of_N(K,N)) + send(N-K, MaxLen);
        if (min > nBits){
            min = nBits;
            Kmin = K;
        }
    };

    memo[N] = min;
    best[N] = Kmin;
    if(MaxLen>=N){
        nBits = ceil(log2_Of_Factorial_N(N));
        if (min>=nBits){
            min = nBits;
            best[N] = N;
        }
    }

    memo[N] = min;
    return min;
};

void find_Sequence_Of_Numbers_Of_Cards(int N){

    cout <<"Send first "<<best[N]<<"\tcards, needs ";
    cout <<ceil(log2_Of_K_Permutation_Of_N(best[N],N));
    cout <<"\tbits for P("<<best[N]<<","<<N<<") permutations, remains "<<N-best[N]<<" cards."<<endl;
    while(N>0){
        N -= best[N];
        if (N<=1) continue;
        cout <<"Send next "<<best[N]<<"\tcards, needs ";
        cout <<ceil(log2_Of_K_Permutation_Of_N(best[N],N));
        cout <<"\tbits for P("<<best[N]<<","<<N<<") permutations, remains "<<N-best[N]<<" cards."<<endl;
    };

    cout <<"Send last card, needs 0 bits (no information needed)"<<endl;
    cout<<endl;
};


int main()
{
    init();
    int N = 52; //number of cards.
    int MaxLen = 18; //Only send at most MaxLen cards at a time;

    int res = send(N, MaxLen);

    cout <<"Sending "<<N<<" cards with at most "<<MaxLen<<" cards at a time:"<<endl<<endl;

    find_Sequence_Of_Numbers_Of_Cards(N);

    cout <<"Total:   "<<res<<" bits required for sending "<<N<<" cards."<<endl;
    cout <<"Optimal: "<<ceil(log2_Of_Factorial_N(N))<<" bits required for sending "<<N<<" cards."<<endl;

    return 0;
}

Sort the cards and a sequential index to cards, then each card has a number between 0-51 (inclusive); which can be represented by 6 bits; hence 6*52, but we can do much better;

send the first card, remove that card from the deck and update the sequence number of the cards, (i.e. remaining the cards will have numbers from 0-50)

- for the first 20 cards you need 6 bits to represent each card: 6*20
Now you have 32 cards left, and each card can be represented by 5 bits;
- for the next 16 cards, you need 5 bits to represent each card: 5*16
Now you have 16 cards left, and each card can be represented by 4 bits;
Now you need 4*8,
and then 3*4,
and then 2*2;
and then 1*1;
Total is: 6*20 + 5*16+ 4*8 + 3*4 + 2*2 + 1*1,
Note that you don't need to send the last card, after knowing the 51 cards, the 52nd card is known :)

you have 52! possible hands
80658175170943878571660636856403766975289505440883277824000000000000

so the best you can do is log2(52!)
225.5810031237028

226
I am glad he did not ask how to decode or encode it but this is the theoretical limit

@ADM and others all have the right approach. 226 bits is the answer. Here is some Javascript for the encode and decode.

(function run() {    
    function GetTxString() {
        var s = new BigNumber(0);    // series
        var max = 52;
        for ( var i=0; i<52; ++i, --max ) {
            var c = rnd(max);        // card 0 to max-1
            s = s.mul(max);          // make room
            s = s.add(c);            // add to series
            //console.log(max, c, s);
        }
        return s.toString(2);        // binary string
    }
    function decomRx(rx) {
        var s = new BigNumber(rx, 2);
        var c = [0];                 // cards, rev order
        for ( var i=2; i<=52; ++i ) {
            c.push(+s.mod(i));
            s = s.divToInt(i);
        }
        //console.log(c, s);
        return c.reverse();          // fix-up tx ordering
    }
    function rnd(max) {
        //return max-1;              // use to demo worst case
        return Math.floor(Math.random()*max);
    }
    BigNumber.config(0);
    var tx = GetTxString();
    console.log(tx);
    console.log(tx.length);
    var cards = decomRx(tx);
    console.log(cards);
})();

As @ADM and others have pointed out, the answer is 226 bits. Here's some JS code:

(function run() {    
    function GetTxString() {
        var s = new BigNumber(0);    // series
        var max = 52;
        for ( var i=0; i<52; ++i, --max ) {
            var c = rnd(max);        // card 0 to max-1
            s = s.mul(max);          // make room
            s = s.add(c);            // add to series
            //console.log(max, c, s);
        }
        return s.toString(2);        // binary string
    }
    function decomRx(rx) {
        var s = new BigNumber(rx, 2);
        var c = [0];                 // cards, rev order
        for ( var i=2; i<=52; ++i ) {
            c.push(+s.mod(i));
            s = s.divToInt(i);
        }
        //console.log(c, s);
        return c.reverse();          // fix-up tx ordering
    }
    function rnd(max) {
        //return max-1;              // use to demo worst case
        return Math.floor(Math.random()*max);
    }
    BigNumber.config(0);
    var tx = GetTxString();
    console.log(tx);
    console.log(tx.length);
    var cards = decomRx(tx);
    console.log(cards);
})();

Basically, we can sort all the permutations and then just send the number of permutation, that would be one number between 1 and 52!

Why not just send the seed for the RNG which was used for shuffling?

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by eric on 2015-11-07.
 */
public class Solution {
    static int m = 52;
    public static void main(String[] args){
        int[] a = new int[m];
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < m; i++){
            list.add(i);
        }

        // generate a deck of cards.
        int max = m;
        for(int i = 0; i < m; ++i, --max){
            int index = (int)(Math.random() * max);
            a[i] = list.remove(index);
        }


        for(int i = 0; i < m; i++){
            System.out.print(a[i] + " ");
        }

        String s = encode(a);
        System.out.println();

        System.out.println("s.length == " + s.length());

        int[] b = decode(s);

        for(int i = 0; i < m; i++){
            System.out.print(b[i] + " ");
        }
    }

    private static String encode(int[] a){
        BigInteger big = new BigInteger("0");
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < m; i++){
            list.add(i);
        }

        int max = m;
        for(int i = 0; i < m; i++, --max){
            big = big.multiply(new BigInteger(String.valueOf(max)));
            big = big.add(new BigInteger(String.valueOf(list.indexOf(a[i]))));
            list.remove(list.indexOf(a[i]));
        }
        return big.toString(2);
    }

    private static int[] decode(String s){
        List<Integer> list = new LinkedList<>();
        for(int i = 0; i < m; i++){
            list.add(i);
        }
        BigInteger big = new BigInteger(String.valueOf(s), 2);
        int[] index = new int[m];
        index[m-1] = 0;
        for(int i = 2; i <= m; i++){
            index[m-i] = big.mod(new BigInteger(String.valueOf(i))).intValue();
            big = big.divide(new BigInteger(String.valueOf(i)));
        }
        int[] ret = new int[m];
        for (int i= 0; i < m; i++){
            ret[i] = list.remove(index[i]);
        }
        return ret;
    }

}

Solution 206bits:
We need to encode two features: card suite and card value. Let's forget about the suit at the moment and start with the card value:
If we had 16 cards in total, one could use a hexadecimal base to represent the card value, hence whole deck can be represented as a 16 digit hexadecimal number. Since we only have have 13 card for each suite we can use 13-base system to represent each card. In 13-based system each card would be represented as a number {0,1.. A B C}.

Now, we also have 4 suits for 13 cards which yields 52 different cards. Similarly, one can now represent each card as a 52-base number, hence the whole deck can be represented as a sequence of 52-base digits, more precisely fifty two of such digits. However, the goal is to represent the deck as a binary number. Let’s convert this 52-base number into a binary system.

This requires n = log2(52^52) ~= 206bits, hence each deck can be uniquely represented as a 206 bit binary number.

The whole process would look like this:
(i) convert shuffled deck (represeted e.g. as a String) into a number consisting of fifty two 52-base digits
(ii) convert this digit into a binary number
transmission
(iii) convert the binary number to 52-base number
(iv) convert this fifty two digit long number into desired deck representation (e.g. String)

Looking forward for more elegant solutions :)

if we number all possible permutations:
n = n!/(n-k)!

n = 52!/(52-6)! = 14658134400

only 34 bits used for identify any of permutation

The solution is to look at the sequence from the end to start.
For the last card, the receiver does not need any bits because he can already determine what the remaining card is given the 51 received card. Thus, this last card needs 0 bits.
Similarly, for the one before last card, the receiver needs 1 bit because there are two remaining possibilities.
Following this paradigm

Thus, the number of bits is
0 + 1x1 + 2x2 + 3x4 + 4x8 + 5x16 + 6x20 = 249 bits

Where are 52! possible permutations of 52 cards (all of them are uniaque of course).
Thus we just need ceil(log_2(52!)) bits to code this number.

There are two possible situations:
1) You have a computer -- simple calculate this equation and you get 226.
2) You have no computer. Just use Stirling's Approximation of n! ~ (n/e)^n * sqrt(2*Pi*n)
and then use logarithms to end this approximation.

I've personally got 52! < 2^265 but may be you will be better =)

I think we can do it in 52 bits with some assumptions.

If we can guarantee that a bit will take less than x time to reach its destination, we can break time up into x-sized pieces and use the time slot the bit is received in as the index into the card array (as per above answers).

We need 51 bits to send the cards, and another bit to signal the start of the stream. In this way, we can transfer all 52 cards with a worse case time of 1378x (Sum of x from 1 to 52, as we can restart the timer immediately after every bit is received, and can shift received cards from the array as above), assuming the deck is in the reverse order as in the array, and a best case time of 52x, assuming the same order as the array.

Now, in practice, I'm not sure how feasible this would really be, but feel free to poke holes anyway.

Each machine should shares a decision graph. Build a decision graph as following:
For the first card, it can be in 52 different position. We need 6 level incomplete tree to place it into any of 52 positions. Build a decision tree that places it into one of 52 positions.
For the second card, it can be in 51 remaining positions which we can number in sequence, skipping one that is already occupied (does not matter which one it is). Similarly, build the tree.
So we build such trees until 2 cards left, in which case we just choose first or second, one decision node.

Connect all this tree as following: Every terminal of previous tree points to the root of next. Note that the terminal should imply which position card had taken based on the condition in the terminal and then you move to the root of next tree, it is ok that there is only one link from terminal and not two.

For a given shuffle, determine the path in the given decision graph and encode this path in binary.

With each flipped over card, there are fewer possibilities in the deck:
{{
int get_required_bits()
{
double bits = 0;
for(int x = 52; x >= 1; --x)
{
bits += log((double)x);
}
return (int)ceil(bits);
}
}}
ans: 157

{{
int get_required_bits()
{
double bits = 0;
for(int x = 52; x >= 1; --x)
bits += log((double)x);
return (int)ceil(bits);
}
}}}

If we count all possible permutations
p = n! / (n-k)!
p = 52!/ (52-6)! = 14658134400

we need only 34 bits to identify any of permutation

only 52 bits are needed

Idea is : int data type has 64 bits ie. can store 64 integers

say we get random sequence as : 1 , 15 , 20 , 30, 52 , 4

so int ans = 0
ans = ans | ( 1 << 1 )
ans = ans | ( 1 << 15 )
ans = ans | ( 1 << 20 )
ans = ans | ( 1 << 30 )
ans = ans | ( 1 << 52 )
ans = ans | ( 1 << 4 )

Now, ans carries now 6 random numbers information. Similarly 52 random numbers can be stored in 52 LSB of integer .

so only sending 52 LSB of ans is enough to get information regarding the sequence