Power set manipulation in Python

Question

I am manipulating a set, so if you have a set(aka:list) of n distinctive elements, then you have 2^n subset. Here I show how:

def powerset(s):
    x = len(s)
    masks = [1 << i for i in range(x)]
    for i in range(1 << x):
        yield [ss for mask, ss in zip(masks, s) if i & mask]

l = list(powerset(["A", "B"]))
print(l)

which gives:

[[], ['A'], ['B'], ['A', 'B']]

Now how can take the above list eliminate the empty list, and merge the last element such that it becomes:

['A', 'B', 'AB']

I want to repeat this procedure 5 times, taking final output and write its sublist, eliminate the empty list and merge those elements that they fall into the same sublist.

First lists, now sets .... why? [YourOtherQuestion](https://stackoverflow.com/questions/49669856/how-to-repeat-an-operation-on-a-list) — Patrick Artner, Apr 05 '18 at 11:12
There is a `itertools` - recipes for powersets: https://docs.python.org/3.6/library/itertools.html#itertools-recipes that you can modidy to exclude the empty set. as well as https://stackoverflow.com/questions/18035595/powersets-in-python-using-itertools — Patrick Artner, Apr 05 '18 at 11:13
"..set(aka:list)"? `Set` and `list` are different in python. — Austin, Apr 05 '18 at 11:25
@PatrickArtner Thanks Patrick indeed I needed to distinguish between the two — , Apr 05 '18 at 11:37

L3viathan · Answer 1 · 2018-04-05T12:08:08.237

1

First, filter out the falsy (empty) elements, then join the elements of the remaining elements:

>>> l = [[], ['A'], ['B'], ['A', 'B']]
>>> list(map(''.join, filter(bool, l)))
['A', 'B', 'AB']

Equivalent list-comprehensiony way:

>>> l = [[], ['A'], ['B'], ['A', 'B']]
>>> [''.join(e) for e in l if e]
['A', 'B', 'AB']

To do this five times, do it five times:

start = ["A", "B"]
for _ in range(5):
    start = [''.join(e) for e in powerset(start) if e]

edited Apr 05 '18 at 12:08

answered Apr 05 '18 at 11:10

L3viathan

26,748
2
58
81

Thanks how can I take the last list meaning ['A', 'B', 'AB'] and do the same procedure on it now? I want to know how to make a for loop inside. So now that I have ['A', 'B', 'AB'] I can have 8 sublist and i want to do the same as before namely eliminate the empty list and merge the ones that are in one sublist – Apr 05 '18 at 11:21
@tobias_k We start by the set ["A","B"] we write the subset after eliminating the empty subset and merging the the elements, so [[], ['A'], ['B'], ['A', 'B']] becomes ['A', 'B', 'AB'], Now I want to take ['A', 'B', 'AB'] and write its subsets in similar manner. And repeat the procedure 5 times – Apr 05 '18 at 11:43
@William Added how to repeat it. – L3viathan Apr 05 '18 at 12:08

tobias_k · Accepted Answer · 2018-04-05T11:41:43.943

To get rid of the empty set, just start your loop with 1 instead of 0, then ''.join:

def powerset(s):
    x = len(s)
    masks = [1 << i for i in range(x)]
    for i in range(1, 1 << x):
        yield ''.join(ss for mask, ss in zip(masks, s) if i & mask)

If you want to repeat this, i.e. get the powerset of the powerset of the original list, just feed the result back into the function in a loop:

lst = ["A", "B"]
for _ in range(5):
    lst = list(powerset(lst))
    print(lst)

Having said that, it might make more sense to do this filtering and joining as a post-processing step, as in @L3viathan's answer, as a true powerset function should neither omit nor modify results.

score 1 · Answer 3 · answered Apr 05 '18 at 11:46

1

data = [[], ['A'], ['B'], ['A', 'B']]
list(filter(None,map(lambda x:''.join(x) if x else None, data)))
>>>['A', 'B', 'AB']

answered Apr 05 '18 at 11:46

Veera Balla Deva

790
6
19

score 0 · Answer 4 · answered Apr 05 '18 at 11:14

0

Maybe you need something like a flatmap?

from itertools import chain, imap

def flatmap(f, items):
        return chain.from_iterable(imap(f, items))

>>> list(flatmap(lambda x: x, [[], ['A'], ['B'], ['A', 'B']]))
['A', 'B', 'A', 'B']

answered Apr 05 '18 at 11:14

Alper

3,424
4
39
45

score 0 · Answer 5 · answered Apr 05 '18 at 11:15

0

Was this what you were looking for:

def powerset(s):
    x = len(s)
    masks = [1 << i for i in range(x)]
    for i in range(1 << x):
        item = ''.join([ss for mask, ss in zip(masks, s) if i & mask])
        if item:
            yield item
l = list(powerset(["A", "B", "C"]))
print(l) 
#['A', 'B', 'AB', 'C', 'AC', 'BC', 'ABC']

I introduced C as it obviously works with A and B.

answered Apr 05 '18 at 11:15

zipa

27,316
6
40
58

Thanks how can I take the last list meaning ['A', 'B', 'AB'] and do the same procedure on it now? I want to know how to make a for loop inside. So now that I have ['A', 'B', 'AB'] I can have 8 sublist and i want to do the same as before namely eliminate the empty list and merge the ones that are in one sublist – Apr 05 '18 at 11:31

Power set manipulation in Python

5 Answers5