2
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Welcome to Code Review. Are you using Python 2.x or 3.x? \$\endgroup\$
    – Phrancis
    Oct 18, 2017 at 18:47
  • \$\begingroup\$ I'm using Python 2.7 \$\endgroup\$ Oct 18, 2017 at 19:55

1 Answer 1

3
\$\begingroup\$

This is , 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 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.