Python Power Set of a List

Question

I am trying to implement a function to generate the powerset of a list xs.

The general idea is that we walk through the elements of xs and choose whether to include x or not. The problem I'm facing is that withX ends up being equal to [None] (a singleton list with None) because (I think) s.add(x) returns None.

This isn't a homework assignment, it's an exercise in Cracking the Coding Interview.

def powerSetBF(xs):
    powerSet = [] 
    powerSet.append(set([]))
    for x in xs:
        powerSetCopy = powerSet[:]
        withX = [s.add(x) for s in powerSetCopy] # add x to the list of sets 
        powerSet = powerSet.extend(withX) # append those entries
    return powerSet

Answer 1

Take a look at the powerset example from the itertools recipes:

from itertools import chain, combinations

def powerset(iterable):
    "list(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))

For a range of integers up to the length of the given list, make all possible combinations and chain them together as one object.