Python Power Set of a List [duplicate]

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

Stroh

could you provide more context? exemplaric input and expected vs. actual output? – Versatile

capturing return value of [s.add(x) for s in powerSetCopy] definitely wrong. It will always be a list of Nones. s.add(x) returns None. – Illustrate

maybe related print powerset of a string – Contract

@Stroh there are quite a few mistakes in this code. e.g. powerSet = powerSet.extend(withX) will assign None to powerSet, as extend modifies in place and returns None. I recommend learning more about list manipulation in python. – Illustrate

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.

Ayeaye

Answer 2

Here's a recursive solution that does not use any modules:

def pset(myset):
  if not myset: # Empty list -> empty set
    return [set()]

  r = []
  for y in myset:
    sy = set((y,))
    for x in pset(myset - sy):
      if x not in r:
        r.extend([x, x|sy])
  return r

print(pset(set((1,2,3,4))))
#[set(), {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}, {4}, 
# {1, 4}, {2, 4}, {1, 2, 4}, {3, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}]

Frutescent

Answer 3

import itertools

def powerset(L):
  pset = set()
  for n in xrange(len(L) + 1):
    for sset in itertools.combinations(L, n):
      pset.add(sset)
  return pset

powerset([1, 2, 3, 4])

result

set([(1, 2), (1, 3), (1, 2, 3, 4), (1,), (2,), (3,), (1, 4), (4,), (), (2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (1, 2, 3), (3, 4), (2, 4)])

Source code for itertools.combinations can be found here which has a few neat optimizations:

https://docs.python.org/3/library/itertools.html#itertools.combinations

Larimer

Note that that code in the docs is "roughly equivalent" to the source code of itertools. combinations, which is implemented in C, so it's more efficient than doing it in pure Python code. – Metaplasia