时间戳

首页 > 解决方案 > 如何并行计算 k 个集合位的所有组合？

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

问题描述

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

我在想像 Gosper's 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);
}

此外，在我的情况下，组合不一定需要按字典顺序排列。只要生成所有组合，任何排序都可以。

标签： cbit-manipulationcombinationscombinatorics

解决方案

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

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)返回 331（101001011二进制，表示{8, 6, 3, 1, 0}），如示例中所示。

推荐阅读