迭代给定大小的所有子集

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的黑客:

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,然后在其二进制扩展中再次出现一堆零.

处理这种"一块"数字的方法是将最高位移一,并尽可能低地击打所有其他位.Gosper的hack通过找到最低设置位(a),找到包含我们不触摸的位的"高部分"和"进位"(b),然后产生一个从最小开始的适当大小的块来工作. - 重要的一点.