迭代所有给定大小的子集

Question

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

那么遍历大小为k (对于(0 <= k <= n))的所有子集呢? 这是个性能噩梦吗? 我知道有(n, k) = n! / k! (n - k)! 种可能性。如果k非常接近0或非常接近n，这个数字就很小。

在n和k方面，最坏情况的表现如何？除了O(n! / k! (n - k)!)之外，还有更简单的说法吗？这是否渐进地小于O(n!)或相同？

- Paul Reiners

---

显然，这取决于n和k的值。你在寻找什么样的答案？ - shx2

Answer 1

你想要Gosper的技巧：

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

解释：

要找到下一个具有相同二进制位数的数字，基本上可以将其简化为具有恰好一个“一块”的数字——在它们的二进制展开中，先是一堆零，然后是一堆一，然后再是一堆零。

处理这种“一块”数字的方法是将最高位左移一位，然后尽可能地将所有其他位向下压缩。Gosper 的技巧通过找到最低位（a），找到包含我们不操作的位和进位位（b）的“高位”，然后产生一个以最低有效位开始的适当大小的一块。

- tmyklebu

Answer 2

对于固定的n，很容易证明(n, k)在k = n/2时取得最大值。如果我没有误用斯特林逼近公式，那么(n, n/2)的渐近行为是指数级别的。

对于常数k，(n, k)是O(n^k)。请记住组合函数是对称的，因此对于(n, n-k)也是一样的。它是多项式级别的，因此比O(n!)小得多。

- bmm6o