Iterate over all subsets of a given size

Question

I know that iterating over all subsets of a set of sizes n is a performance nightmare and will take O (2 ^ n) time.

How about iterating over all subsets of size k (for (0 <= k <= n))? A nightmare? I know that there is (n, k) = n! / K! (n - k)! opportunities. I know that if k is very close to 0 or very close to n, this is a small number.

What is the worst performance in terms of n and k? Is there an easier way to say this differently than just O (n! / K! (N - k)!)? Is it asymptotically smaller than O (n!) Or the same?

Answer 1

Do you want to hack 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; } 

Explanation:

The search for the next number with so many bits usually comes down to the case of numbers with exactly one “block of them” —numbers having a bunch of zeros, then a bunch of ones, then a bunch of zeros again in their binary decompositions.

A way to deal with such a number of “unit blocks” is to move the highest bit left by one and reset all the others as low as possible. The gosper hack works by picking the bit with the smallest set ( a ), finding the “high part” containing the bits that we don’t touch, and the “carry bit” ( b ), then creating a block from the corresponding ones whose size starts with the least significant bit.

Answer 2

It is easy to show that for fixed n , (n, k) has a maximum for k = n/2 . If I misused the Stirling approximation, the asymptotic behavior for (n, n/2) exponential.

For the constant k , (n, k) - O(n^k) . Keep in mind that the combinatorial function is symmetric, therefore it is the same for (n, nk) . This is a polynomial, so it is smaller than O(n!) .