7

Suppose we need to write a function that gives the list of all the subsets of a set. The function and the doctest is given below. And we need to complete the whole definition of the function

def subsets(s):
   """Return a list of the subsets of s.

   >>> subsets({True, False})
   [{False, True}, {False}, {True}, set()]
   >>> counts = {x for x in range(10)} # A set comprehension
   >>> subs = subsets(counts)
   >>> len(subs)
   1024
   >>> counts in subs
   True
   >>> len(counts)
   10
   """
   assert type(s) == set, str(s) + ' is not a set.'
   if not s:
       return [set()]
   element = s.pop() 
   rest = subsets(s)
   s.add(element)

It has to not use any built-in function

My approach is to add "element" into rest and return them all, but I am not really familiar how to use set, list in Python.

geraldgreen
  • 192
  • 1
  • 1
  • 7
  • What do you mean by `set of all subsets`? I picture [this](http://en.wikipedia.org/wiki/Power_set). Are you just looking for all the possible combinations of items? – Blender Nov 02 '11 at 23:43
  • Yes, that's what I meant but exclude the empty set – geraldgreen Nov 02 '11 at 23:45
  • 2
    Be careful using sets or dicts with doctests. The output order isn't guaranteed, so it is typically better to write something like: ``sorted(map(list, subsets(somepool)))``. That way the output is deterministic. – Raymond Hettinger Nov 02 '11 at 23:54

7 Answers7

17

Look at the powerset() recipe in the itertools docs.

from itertools import chain, combinations

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))

def subsets(s):
    return map(set, powerset(s))
Raymond Hettinger
  • 216,523
  • 63
  • 388
  • 485
  • That one's pretty inefficient, though. – ephemient Nov 02 '11 at 23:47
  • 1
    The powerset() recipe is the fastest on record. Formerly, the fastest was a bit flipping version by Eric Raymond. The only slow part is building all the individual sets, but that was part of the OP's requirement. – Raymond Hettinger Nov 03 '11 at 00:03
3
>>> s=set(range(10))
>>> L=list(s)
>>> subs = [{L[j] for j in range(len(L)) if 1<<j&i} for i in range(1,1<<len(L))]
>>> s in subs
True
>>> set() in subs
False
John La Rooy
  • 295,403
  • 53
  • 369
  • 502
  • This is very close to the Eric Raymond version that was published in old versions of the itertools docs. His, of course, pre-dates list and set comprehensions. – Raymond Hettinger Nov 03 '11 at 00:41
0

Slightly more efficient (less copying around than in previous answers):

# Generate all subsets of the list v of length l.
def subsets(v, l):
  return _subsets(v, 0, l, [])

def _subsets(v, k, l, acc):
  if l == 0:
    return [acc]
  else:
    r = []
    for i in range(k, len(v)):
      # Take i-th position and continue with subsets of length l - 1:
      r.extend(_subsets(v, i + 1, l - 1, acc + [v[i]]))
    return r
Andrei Sfrent
  • 189
  • 1
  • 11
0

If you want to get all subsets without using itertools or any other libraries you can do something like this.

def generate_subsets(elementList):
    """Generate all subsets of a set""" 
    combination_count = 2**len(elementList)

    for i in range(0, combination_count):   
        tmp_str = str(bin(i)).replace("0b", "")
        tmp_lst = [int(x) for x in tmp_str]

        while (len(tmp_lst) < len(elementList)):
            tmp_lst = [0] + tmp_lst

        subset = list(filter(lambda x : tmp_lst[elementList.index(x)] == 1, elementList))
        print(subset)
hddananjaya
  • 76
  • 2
  • 10
0
>>> from itertools import combinations
>>> s=set(range(10))
>>> subs = [set(j) for i in range(len(s)) for j in combinations(s, i+1)]
>>> len(subs)
1023
John La Rooy
  • 295,403
  • 53
  • 369
  • 502
0

The usual implementation of powerset on list goes something like this:

def powerset(elements):
    if len(elements) > 0:
        head = elements[0]
        for tail in powerset(elements[1:]):
            yield [head] + tail
            yield tail
    else:
        yield []

Just needs a little bit of adaptation to deal with set.

ephemient
  • 198,619
  • 38
  • 280
  • 391
  • 1
    I like this one. It is a classic. OTOH, it is dog slow with all the list concatenations, and recursive calls (each with a global look up). – Raymond Hettinger Nov 03 '11 at 00:40
-1
>>> from itertools import combinations
>>> s=set([1,2,3])
>>> sum(map(lambda r: list(combinations(s, r)), range(1, len(s)+1)), [])
[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

produces tuples, but it is close enough for you

Lachezar
  • 6,523
  • 3
  • 33
  • 34