I'm looking for a simple way to generate the powerset of an iterable where each element can be "positive" or "negative", but not both in the same combination. There are no duplicates in the iterable and only the element or it's negative. Order doesn't matter.
Here is an example with a list of int
's:
The iterable:
elements = [-2, 1]
The desired powerset:
[]
[-2]
[2]
[-1]
[1]
[-2, -1]
[-2, 1]
[2, -1]
[2, 1]
"Subsets" to exclude:
[-1, 1]
[-2, 2]
My current approach is to use the powerset implementation from here for the combined list of elements
and [-x for x in elements]
and then iterate through the powerset and remove unwanted combinations.
However, that's not optimal I guess.
Is there a simple solution that doesn't require me to remove unwanted combinations in the end?
Each element can be included, included negated, or excluded. Use itertools.product
to go through all 3**len(elements)
possible ways to pick an option for each element:
import itertools
def extended_powerset(elements):
elements = list(elements)
n = len(elements)
for option in itertools.product([-1, 0, 1], repeat=n):
yield [i*elem for (i, elem) in zip(option, elements) if i]