performance - 迭代给定大小的所有子集

Question

我知道迭代一组大小为 n 的所有子集是性能噩梦，需要 O(2^n) 时间。

如何迭代大小为 k 的所有子集(for (0 <= k <= n))？这是一场表演噩梦吗？我知道有 (n, k) = n!/k! (n - k)!可能性。我知道如果 k 非常接近 0 或非常接近 n，这是一个很小的数字。

就 n 和 k 而言，最坏情况下的性能是什么？除了 O(n!/k! (n - k)!) 之外，还有更简单的表达方式吗？这是渐近小于 O(n!) 还是相同？

Answer 1

你想要 Gosper 的 hack:

int c = (1<<k)-1;
while (c < (1<<n)) {
  dostuff(c);
  int a = c&-c, b = c+a;
  c = (c^b)/4/a|b;
}

解释:

找到下一个设置了尽可能多的位的数字基本上减少了只有一个“1块”的数字的情况——数字有一堆零，然后是一堆1，然后在它们的二进制扩展中又是一堆零.

处理这样一个“1 块”数字的方法是将最高位移动到 1 位，并尽可能地将其他所有位猛击到低位。 Gosper 的 hack 通过找到最低设置位( a )，找到包含我们未触及的位和“进位位”( b )的“高位部分”，然后生成适当的块从最低有效位开始的大小。