如何并行计算k个集合位的所有组合？

Question

我想有效地计算一个n位数字（在我的例子中，n=36)的所有组合，并且设置了精确的k位。

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

Answer 1

您可以按照以下示例实现它：

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

调用to_composition(5,72)返回331(101001011二进制格式，表示{8,6,3,1,0})，如示例所示。