如何并行计算k组位的所有组合?

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

我想有效地计算一个 n 位数字(在我的例子中,n=36)的所有组合,正好设置了 k 位。

我在想 Gosper 的 Hack,但可以并行化。

例如,如果我可以将索引传递给 Gosper's Hack,它会计算出第 i 个组合,那就太完美了。

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

此外,就我而言,这些组合不一定需要按字典顺序排列。只要生成所有组合,任何排序都可以。

您可以按照下面的方式实现它,遵循 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));
}

调用to_combination(5, 72) returns 331(101001011二进制,表示{8, 6, 3, 1, 0}),如示例。