## Generating powerset: beauty vs. speed

Consider the following “beautiful” implementation:

public IEnumerable<IEnumerable<T>> GetPowerset<T>(IEnumerable<T> set) { if (!set.Any()) yield break; T head = set.First(); var tail = set.Skip(1); bool isTailEmpty = !tail.Any(); yield return Singlet(head); if (!isTailEmpty) { var ps = GetPowerset(tail); foreach (var subset in ps) { yield return subset; yield return subset.Concat(Singlet(head)); } } } IEnumerable<T> Singlet<T>(T x) { yield return x; }

(BTW, I know that my Singlet can be written as Enumerable.Repeat(x, 1), but I think the word “singlet” loks more beautiful 😉

Okay, this algorithm has a problem: it is slow. The “binary counter” algorithm below works much, much faster:

public IEnumerable<IEnumerable<T>> GetPowerset<T>(List<T> set) { byte[] counter = new byte[set.Count]; for (int count = 0; count < (1 << set.Count) - 1; count++) { bool carry = true; int digit = 0; while (carry) { if (counter[digit] == 0) { counter[digit] = 1; carry = false; } else { counter[digit] = 0; carry = true; } digit++; } var q = from i in Enumerable.Range(0, set.Count) where counter[i] == 1 select set[i]; yield return q; } }

(See, it still uses Linq, so it’s not completely ugly 😉

What’s funny is that I ended up throwing away both of these algorithms. I initially attempted to implement subanagram generation by using powersets, but the speed was unacceptable regardless of the implementation, and I soon discovered that there is a much faster approach. So what I described above was real Premature Optimization. But was it Evil? Not at all. First of all, it could have potentially solved the problem. And even though it didn’t, it indicated that some other optimizations needed to be done

## Leave a Reply