Consider the 52 cards of a deck. You generated a random sequence for these cards and want to send that sequence to a receiver. You want to minimize the communication between you and the receiver, i.e., minimize the number of bits required to send the sequence.So first, how to come up with 6 * 52? Each card is in the range 1 - 52, so if we use 6 bits, there are 2^6 = 64 possibilities, which can cover all possible sequences.
What is the minimum number of bits required to send the sequence?
Hint: It is not 6 x 52
Now we know that the bits required must include all possible sequences of that 52 cards, so how many possibilities? (52!). This means that we need n bits that 2^n >= (52!), so the theoretical answer is that we need log2(52!) = 226 bits.
So how to get that limit?
The first approach( besides the 6 * 52 one):
We know that the first card has 52 possibilities, the second has 51, ..., the 20th has 33 possibilities, so for the first 20 cards, we need at least 6 bits for each.
Then the 21st has 32 possibilities, ... 36th has 17 possibilities, so the next 16 cards we need at least 5 bits.
Then the next 8 cards we need 4 bits.
Then 4 cards, 3 bits.
Then 2 cards, 2 bits.
Then 1 card, 1 bit.
And after we know 51 cards, we know what the 52th is, so we don't need any bits. Thus in total:
20 * 6 + 16 * 5 + 8 * 4 + 4 * 3 + 2 * 2 + 1 = 249 bits. This solution is still larger.
The second one:
Consider we first send out k cards, which needs at most log2(Permu(k, 52)) bits, and now we have 52 - k cards. So we compute from 1 to 52 the k that can give us the minimum total bits required. We use recursion. Moreover, at each calling, the smaller number is already calculated, so we use an array to store at each n, the minimum bits required, thus can reduce some recursions.
However, Java has some problems with rounding (e.g., permu(1, 6) should return 3, but I get 4), so I cannot reach the optimized solution. See here for the C++ solution that can get to 227 bits.
public class SendingCards {
static int N = 52;
//Given n cards, best number of cards sent
//static int[] cardsSent = new int[N + 1];
static int[] minBits = new int[N + 1];
static{
minBits[1] = 0;
minBits[2] = 1;
minBits[3] = 3;
//given 2 cards, sent 1 card first
//cardsSent[1] = 1;
//cardsSent[2] = 1;
//cardsSent[3] = 3;
}
public static double logFact(int n){
if(n == 0)
return 0;
double rst = 0;
for(int i = 1; i <= n; i++)
rst += Math.log((double)n) / Math.log(2.0);
return rst;
}
public static double logPerm(int k, int n){
//System.out.format("%d, %d: %.4f\n", k, n, logFact(n) - logFact(n - k));
return logFact(n) - logFact(n - k);
}
//maxSent can be changed, after certain recursions, the number should converge
//so we don't need to calculate from 1 to 52
public static int send(int n, int maxSent){
if(n <= 1)
return 0;
if(n == 2)
return 1;
if(n == 3)
return 3;
//if minBits have been calculated before, return the previous solution
if(minBits[n] > 0)
return minBits[n];
int min = Integer.MAX_VALUE;
int bits = 0;
int kmin = 0;
for(int k = 1; k <= Math.min(maxSent, n); k++){
bits = (int)Math.ceil(logPerm(k, n)) + send(n - k, maxSent);
if(min > bits){
min = bits;
kmin = k;
}
}
System.out.println("n: " + n + ", min: " + min);
//cardsSent[n] = kmin;
minBits[n] = min;
return min;
}
public static void main(String[] args) {
System.out.println(send(N, 16));
}
}
