Depth-first enumeration of powerset (of ordered set)

Question

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.

score 2 · Accepted Answer · answered Jul 18 '22 at 00:30

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]

score 1 · Answer 2 · answered Jul 17 '22 at 23:50

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

Jackson H · Answer 3 · 2022-07-18T00:06:06.737

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

edited Jul 18 '22 at 00:06

answered Jul 18 '22 at 00:00

Jackson H

171
10

That answer doesn’t generate the subsets in the desired order, unfortunately. – kc9jud Jul 18 '22 at 00:01
@kc9jud You are right, thanks for pointing it out. – Jackson H Jul 18 '22 at 00:05

score 0 · Answer 4 · answered Jul 18 '22 at 07:34

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

Depth-first enumeration of powerset (of ordered set)

4 Answers4