Sunday, March 29, 2015

Minimum bits required to send a sequence of a deck of cards


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.
What is the minimum number of bits required to send the sequence?
Hint: It is not 6 x 52
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.

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));

 }

}

1 comment:

  1. The development of artificial intelligence (AI) has propelled more programming architects, information scientists, and different experts to investigate the plausibility of a vocation in machine learning. Notwithstanding, a few newcomers will in general spotlight a lot on hypothesis and insufficient on commonsense application. IEEE final year projects on machine learning In case you will succeed, you have to begin building machine learning projects in the near future.

    Projects assist you with improving your applied ML skills rapidly while allowing you to investigate an intriguing point. Furthermore, you can include projects into your portfolio, making it simpler to get a vocation, discover cool profession openings, and Final Year Project Centers in Chennai even arrange a more significant compensation.


    Data analytics is the study of dissecting crude data so as to make decisions about that data. Data analytics advances and procedures are generally utilized in business ventures to empower associations to settle on progressively Python Training in Chennai educated business choices. In the present worldwide commercial center, it isn't sufficient to assemble data and do the math; you should realize how to apply that data to genuine situations such that will affect conduct. In the program you will initially gain proficiency with the specialized skills, including R and Python dialects most usually utilized in data analytics programming and usage; Python Training in Chennai at that point center around the commonsense application, in view of genuine business issues in a scope of industry segments, for example, wellbeing, promoting and account.

    ReplyDelete