Rank of n-bit numbers with exactly k bits set

This problem is a follow-up of the post titled: Generate the next integer with the same number of bits. If we list all n bit integers which have exactly k bits set to 1, what will be the rank of a given number in that list ? For example, if n=4, k=2, then there are 6 (n choose 2) such numbers, and after listing them by increasing order, the ranking is as follows.

0011 => 0
0101 => 1
0110 => 2
1001 => 3
1010 => 4
1100 => 5

The question is given the bit pattern, as an array of booleans, what is the efficient way to directly compute the rank ? This problem can be handled by examining one element at a time. To formulate the solution, let the notation C(n,k) indicates n choose k.

Examine the most significant bit. If it is zero that bit can be dropped and the problem reduces to a sub-problem of size (n-1,k), and its solution to the original problem is the same as the solution to this sub-problem. If the most significant bit is one, then the problem reduces to a sub-problem of size (n-1,k-1), but in this case we have to add C(n-1,k) to the solution of the subproblem to get the solution to the original problem.

In general the C(n,k) combinations consists of C(n-1,k) patterns which start with zero, and C(n-1,k-1) patterns which start with ones. Recall the identity :

C(n,k) = C(n-1,k) + C(n-1,k-1)

This translates to a recursive algorithm, and since the recursion is only tail-recursion it is readily converted into an iterative algorithm, as follows :

1 2 3 4 5 6 7 8 9 10

long GetSequenceId(vector<bool>& array, int k) { long rank = 0; for (int i = array.size()-1; i >= 0; --i) { if (array[i] == true) { rank += Combination(i,k); --k; } } return rank; }

The combination can be pre-computed as a table, using Pascal's triangle. However this algorithm can be made even faster by reversing the direction of the loop, and computing the combinations on-the-fly. Here goes the C++ code.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

uint64_t GetSequenceId(vector<bool>& array) { uint64_t rank = 0, nck = 1; uint32_t numones = 0; for (int i = 0; i < array.size(); ++i) { if (array[i]) { ++numones; nck = (numones == i) ? 1 : (nck * i / numones); rank += nck; } else { nck = (numones >= i) ? 1 : nck * i / (i - numones); } } return rank; }

Generate the next integer with the same number of bits.

The statement of the algorithm is as follows :
Given an integer N, what is the next higher number with the same number of bits. Write an algorithm to produce the same, return error if the given number is already the highest number with the same number of bits.

The code given below works on a vector of boolean. However it would be straight-forward to convert it to bit manipulation routine. There is also an alternate brute-force implementation, and the main method tests that the two produce the same output.

#include <cassert>
#include <cstdio>
#include <cstdint>
#include <string>
#include <vector>
using namespace std;

// Locate the first zero followed by some 1. If there is no such zero,
// return false, because the permutation cannot be incremented.
// Once found set it 1, shifting all the remaining 1's encountered so
// far to the right end.
bool GenerateNextInterleaving(vector<bool>& array) {
  int onbits = 0;
  int i = 0;
  for (; i < array.size(); ++i) {
    if (array[i]) {
      ++onbits;
      array[i] = false;
    } else if (onbits > 0) {
      // It is the first zero followed by some 1.
      array[i] = true;
      break;
    }
  }
  if (i >= array.size()) {
    return false;
  }
  for (i = 0; i < (onbits-1); ++i) {
    array[i] = true;
  }
  return true;
}

// Iterate through all possible combinations, with given total bits,
// and number of on bits.
void GenerateAllInterleavings(int numbits, int onbits,
                        vector<string>* outputs) {
  vector<bool> array(numbits, false);
  for (int i = 0; i < numbits && i < onbits; ++i) {
    array[i] = true;
  }
  char buffer[numbits + 1];
  buffer[numbits] = '\0';
  do {
    for (int i = 0; i < numbits; ++i) {
      buffer[i] = array[numbits-1-i] ? '1' : '0';
    }
    printf("algorithm's solution: %s\n", buffer);
    outputs->push_back(buffer);
  } while (GenerateNextInterleaving(array));
}

// A brute force version to test the above algorithm.
void BruteForceSolution(int size, int onbits, vector<string>* outputs) {
  uint64_t limit = (1UL << size);
  char buffer[size + 1];
  buffer[size] = '\0';
  for (uint64_t n = 0; n < limit; ++n) {
    // Count number of bits in n.
    int count = 0;
    for (uint64_t copy = n; copy; copy >>= 1) {
      if (copy & 0x1) ++count;
    }
    if (count == onbits) {
      uint64_t copy = n;
      for (int i = 0; i < size; ++i) {
        buffer[size - 1 - i] = (copy & 0x1) ? '1' : '0';
        copy >>= 1; 
      }
      printf("brute-force solution %s\n", buffer);
      outputs->push_back(buffer);
    }
  }
}

int main() {

  int numbits = 8, onbits = 3;

  // Ensure that the algorithm produces the same output as the
  // brute-force solution.
  vector<string> bruteforce_result;
  BruteForceSolution(numbits, onbits, &bruteforce_result);

  vector<string> algo_result;
  GenerateAllInterleavings(numbits, onbits, &algo_result);

  assert(algo_result == bruteforce_result);
  return 0;
}

Crate Google App-Engine Project in Maven

Start a new project using apache Maven :

APP_ID=<your-app-id>  // e.g. magnetic-clone-xxx
mvn archetype:generate -Dappengine-version=1.9.15 -Dapplication-id=${APP_ID}
  -Dfilter=com.google.appengine.archetypes:

Some additional packages required for app-engine :
Add the dependency to the pom.xml file in the maven project.

• GCS Client :
   

  <dependency>
  <groupId>com.google.appengine.tools</groupId>
  <artifactId>appengine-gcs-client</artifactId>
  <version>RELEASE</version>
  </dependency>
  

• Datastore protobuf API :
   

  <dependency>
  <dependency>
   <groupId>com.google.apis</groupId>
   <artifactId>google-api-services-datastore-protobuf</artifactId>
   <version>v1beta2-rev1-2.1.0</version>
  </dependency>
  

• google-api-client-java6 :
   

  <dependency>
  <dependency>
    <groupId>com.google.api-client</groupId>
    <artifactId>google-api-client-java6</artifactId>
    <version>1.18.0-rc</version>
  </dependency>
  

• google-oauth-client-jetty :
   

  <dependency>
  <dependency>
   <groupId>com.google.oauth-client</groupId>
   <artifactId>google-oauth-client-jetty</artifactId>
   <version>1.11.0-beta</version>
  </dependency>
  

Maven 3.2.1 - Installation notes

This version is compatible Google app-engine.

sudo apt-get remove maven*
sudo apt-get install gdebi
wget http://ppa.launchpad.net/natecarlson/maven3/ubuntu/pool/main/m/maven3/maven3_3.2.1-0~ppa1_all.deb
sudo gdebi maven3_3.2.1-0~ppa1_all.deb
sudo ln -s /usr/share/maven3/bin/mvn /usr/bin/maven