How to compute the all combinations of k set bits in parallel?

user_6637939 0
Viewed 118

I want to efficiently compute all combinations of an n-bit number (in my case, n=36) with exactly k bits set.

I am thinking something like Gosper's Hack, but parallelizable.

For example, it would be perfect if I could just pass in an index to Gosper's Hack, and it would compute the i'th combination.

unsigned long long permute(unsigned long long val, unsigned long long i)
{
    int ffs = __builtin_ffsll(val);
    val |= (val - 1);

    // Do something here with `i` to produce the i'th combination, rather than the next one.

    return (val + 1) | (((~val & -(~val)) - 1) >> ffs);
}

Also, in my case, the combinations don't necessarily need to be in lexicographical order. Any ordering will do as long as all combinations are generated.

combinations combinatorics bit-manipulation c
1 Answers

You can implement it as below, following this example:

long to_combination(int k, int N) {
  if (N == 0) {
    return (1L<<k)-1;
  }
  int n;
  for (n=k; C(n,k)<=N; n++)
    ;
  n--;
  return (1L<<n) | to_combination(k-1, N - C(n,k));
}

Calling to_combination(5, 72) returns 331 (101001011 in binary, representing {8, 6, 3, 1, 0}), as in the example.

user_39215130
Related