0

Given an ordered set [1,2,3,...] of elements, how do I enumerate the powerset of this set in a depth-first way? That is, I want to see all of the subsets containing 1 before I see any subsets without 1, then all of the remaining subsets containing 2 (but not 1) before subsets without 2 (or 1), etc.

That is, for the set [1,2,3,4], I want to generate the following tuples in order:

()
(1,)
(1, 2)
(1, 2, 3)
(1, 2, 3, 4)
(1, 2, 4)
(1, 3)
(1, 3, 4)
(1, 4)
(2,)
(2, 3)
(2, 3, 4)
(2, 4)
(3,)
(3, 4)
(4,)

Ideally, I'd be able to do this in a recursive way, without needing to keep track of which subsets I've already visited.

4 Answers 4

2
def powerset(items):
    # yields all sequences that start with prefix, and contain
    # at least one element of items, in order
    def internal(prefix, items):
        if not items:
            return
        first, *rest = items
        yield [*prefix, first]
        yield from internal([*prefix, first], rest)
        yield from internal(prefix, rest)

    yield []
    yield from internal([], items)

And then:

for x in powerset([1, 2, 3, 4]):
    print(x)

[]
[1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 4]
[1, 3]
[1, 3, 4]
[1, 4]
[2]
[2, 3]
[2, 3, 4]
[2, 4]
[3]
[3, 4]
[4]
1
  • Clever -- this avoids loops.
    – kc9jud
    Commented Jul 18, 2022 at 3:48
1

The key here is to see that we can take a single element, and then prepend it to the powerset of the elements which come after it. That is, first we take 1 and generate the powerset of [2,3,4], and prepend 1 to each subset.

(1,) + ()         -> (1,)
(1,) + (2,)       -> (1, 2)
(1,) + (2, 3)     -> (1, 2, 3)
(1,) + (2, 3, 4)  -> (1, 2, 3, 4)
(1,) + (2, 4)     -> (1, 2, 4)
(1,) + (3,)       -> (1, 3)
(1,) + (3, 4)     -> (1, 3, 4)
(1,) + (4,)       -> (1, 4)

Then we take the next element (2), and prepend it to the powerset of the following elements ([3,4]):

(2,) + ()         -> (2,)
(2,) + (3,)       -> (2, 3)
(2,) + (3, 4)     -> (2, 3, 4)
(2,) + (4,)       -> (2, 4)

and so on, until we run out of elements.

We can do this with a python generator:

def powerset(seq):
    def _powerset(seq, elm):
        yield seq
        for i in range(len(elm)):
            yield from _powerset(seq+(elm[i],), elm[i+1:])
    yield from _powerset(tuple(), list(seq))
0

Edit: Unfortunately this does not generate the powerset in the desired order.


As per this answer, it seems other users have found the builtin itertools implementation to be the fastest:

from itertools import chain, combinations

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
2
  • That answer doesn’t generate the subsets in the desired order, unfortunately.
    – kc9jud
    Commented Jul 18, 2022 at 0:01
  • @kc9jud You are right, thanks for pointing it out.
    – Jackson H
    Commented Jul 18, 2022 at 0:05
0

You can use recursion to traverse in DFS fashion to get this result.
Below is an example program.

def powerset(arr):
    subsets=[]
    for i in range(len(arr)):
        subsets.append([arr[i]])
        for j in powerset(arr[i+1:]):
            subsets.append([arr[i]]+j)
    return subsets

Output:

[[1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 4]
[1, 3]
[1, 3, 4]
[1, 4]
[2]
[2, 3]
[2, 3, 4]
[2, 4]
[3]
[3, 4]
[4]]

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.