6

I know that iterating over all subsets of a set of size 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))? Is that a performance nightmare? I know there are (n, k) = n! / k! (n - k)! possibilities. I know that if k is very close to 0 or very close to n, this is a small number.

What is the worst case performance in terms of n and k? Is there a simpler way of saying it other than just O(n! / k! (n - k)!)? Is this asymptotically smaller than O(n!) or the same?

Paul Reiners
  • 8,576
  • 33
  • 117
  • 202
  • obviously, this depends on the values of `n` and `k`. what kind of answer are you looking for? – shx2 Apr 10 '13 at 17:16

2 Answers2

11

You want Gosper's 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;
}

Explanation:

Finding the next number with as many bits set basically reduces to the case of numbers with exactly one "block of ones" --- numbers having a bunch of zeroes, then a bunch of ones, then a bunch of zeroes again in their binary expansions.

The way to deal with such a "block of ones" number is to move the highest bit left by one and slam all the others as low as possible. Gosper's hack works by finding the lowest set bit (a), finding the "high part" comprising the bits we don't touch and the "carry bit" (b), then producing a block of ones of the appropriate size that begins at the least-significant bit.

tmyklebu
  • 13,915
  • 3
  • 28
  • 57
0

It's easy to show that for a fixed n, (n, k) has a maximum at k = n/2. If I haven't misapplied Sterling's approximation, the asymptotic behavior for (n, n/2) is exponential.

For constant k, (n, k) is O(n^k). Keep in mind that the combinatorial function is symmetric, so it's the same for (n, n-k). It's polynomial, so it's way smaller than O(n!).

bmm6o
  • 6,187
  • 3
  • 28
  • 55