Powersets of a list?

[Tim Peters]

[Bengt Richter]
> What about the effect of garbage collection? To be fair, shouldn't all
> timings be started after a fresh garbage collection, at least on an
> algorithm basis, if not each invocation?

The bulk of garbage collection in CPython is done by reference counting, and
objects normally go away as soon as their last reference goes away.  That's
"fair" across algorithms, in the sense that they'll pay for the amount of
trash they create while they're running.

There's another scheme, though, for cleaning up trash with cycles, which
reference counting alone can't discover.  This is triggered by "excess"
allocations:  if, since the last time this pass ran, the number of
allocations is greater than the number of destructions by a certain amount,
this other scheme kicks in, and searches *everything* for the possibility of
trash cycles.  So when you're, say, creating oodles and oodles of lists, but
not destroying them, the cycle-detection system gets triggered often.

That's also fair (in some sense <wink>), but much subtler.  To see the
effect on a particular algorithm, it's easiest to disable that form of gc
for the duration:

import gc
gc.disable()
# run the algorithm; report times
gc.enable()

It *usually* doesn't make much difference (a few percent).