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

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!) 还是相同？

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 块”数字的方法是将最高位向左移动一个，并将所有其他位尽可能低。Gospera的hack 通过找到最低设置位 ( b- 重要的位。

Answer 2

很容易证明，对于一个固定的n，(n, k)有一个最大值在k = n/2。如果我没有误用 Sterling 的近似值，则 的渐近行为(n, n/2)是指数的。

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