I've written the following code for computing the powerset of a list (we consider the list has all distinct elements, although it doesn't really matter).
Can this function be further optimized?
def powerset(A):
if A == []:
return [[]]
a = A[0]
incomplete_pset = powerset(A[1:])
rest = []
for set in incomplete_pset:
rest.append([a] + set)
return rest + incomplete_pset
This is reinventing-the-wheel, because the official documentation gives a recipe:
def powerset(iterable):
"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
By using iterables it tackles the memory-optimization issue effectively.
However, it is possibly not as efficient as it could be because of the way it splits up the work.
To make your code more memory efficient, you could also introduce iterables. I'm assuming that you don't care about the order:
def powerset(A):
if A == []:
yield []
else:
a = A[0]
for tail in powerset(A[1:]):
yield tail
yield [a] + tail
I've chosen tail to avoid aliasing the built-in set function.
The fastest memory-efficient approach is probably going to be an iterable using a Gray code to create a non-recursive solution which adds or removes a single element to the set between each yield.
Also, FWIW, your code could be more Pythonic.
rest = [] for set in incomplete_pset: rest.append([a] + set)
could be
rest = [[a] + tail for tail in incomplete_pset]
It's possible that my iterable rewrite of it could also be more Pythonic using a comprehension - I'm open to comments on this point.
