對給定大小的所有子集進行迭代

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

你要高斯帕的黑客：

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）的「高位部分」，然後生成一個大小適當的塊最不重要的位。

Answer 2

很容易證明，對於固定的n,(n, k)的最大值爲k = n/2。如果我沒有誤用Sterling的近似值，則(n, n/2)的漸近行爲是指數型的。

對於常數k,(n, k)是O(n^k)。請記住，組合函數是對稱的，所以(n, n-k)也是如此。它是多項式的，因此比O(n!)更小。