Depth-first enumeration of powerset (of ordered set)-CodePudding

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.

CodePudding user response：

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

CodePudding user response：

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

CodePudding user response：

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]