Python inverse power set generator

Question

I am trying to get an inverse power set generator, a generator that returns power sets from largest to smallest.

Here is a standard power set generator (see this question):

from itertools import chain, combinations
def powerset_generator(i):
    for subset in chain.from_iterable(combinations(i, r) for r in range(len(i)+1)):
        yield list(subset)

Which generates this:

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

And I'm trying for this:

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

Is there any way to reverse the generator so that it works from the back?

Padraic Cunningham · Accepted Answer · 2015-12-12T22:43:07.313

3

You can set a flag and reverse the range:

def powerset_generator(it, rev=False):
    rn = range(len(it), 0, -1) if rev else range(1, len(it)+1)
    for subset in chain.from_iterable(combinations(it, r) for r in rn):
        yield list(subset)

Using python 3 you could also use yield from in place of chain and map to list which I think reads a bit nicer :

def powerset_generator(it, rev=False):
    rn = range(len(it), 0, -1) if rev else range(1, len(it) + 1)
    for r in rn:
        yield from map(list,combinations(it, r))

If you want an empty lists set the start and stop accordingly:

In [3]: list(powerset_generator([1, 2, 3]))
Out[3]: [[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

In [4]: list(powerset_generator([1, 2, 3],True))
Out[4]: [[1, 2, 3], [1, 2], [1, 3], [2, 3], [1], [2], [3]]

edited Dec 12 '15 at 22:43

answered Dec 12 '15 at 21:51

Padraic Cunningham

176,452
29
245
321

Actually neither of our solutions does what OP desired :D In the example the order of equal sized subsets are reversed too – Tamas Hegedus Dec 12 '15 at 22:30
@hege_hegedus, I think/hope that may is a mistake – Padraic Cunningham Dec 12 '15 at 22:38
The example is wrong, I just posted the reversed list generated from the normal order, will change for future googlers – byrass Dec 12 '15 at 22:54

score 1 · Answer 2 · answered Dec 12 '15 at 21:44

You can start with the bigger subsets. Reverse the range which selects the size, like this:

from itertools import chain, combinations
def powerset_generator(i):
    for subset in chain.from_iterable(combinations(i, r) for r in range(len(i), -1, -1)):
        yield list(subset)

Python inverse power set generator

2 Answers2