I have a list say lis1 = [1,2,3]
and a list of subset of above list say
lis2 = [[1,2],[2,3],[3],[1],[2]]
I want to generate all combinations of lis2 such that all items of lis1 should present in the combination.
For eg. this is a valid combinations
one such combination is [[1,2],[2,3]] (all items of lis1 i.e [1,2,3] is present in it)
whereas this is not
[[1,2],[1],[2]] # (3 is not present in it)
What I did was generated powerset of lis2 via this function
from itertools import chain, combinations
def powerset(iterable):
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(1,len(s)+1))
But as obvious the returning set contain combinations which are of type
[[1,2],[1],[2]] # (3 is not present in it)
How do I check for the combinations which contain all the item of lis1
You can apply your powerset function to get combinations of subsets and filter the results:
>>> lis1 = [1,2,3]
>>> lis2 = [[1,2],[2,3],[3],[1],[2]]
>>> filter(lambda s: set(sum(s,[])) == set(lis1), powerset(lis2))
[([1, 2], [2, 3]),
([1, 2], [3]),
([2, 3], [1]),
([1, 2], [2, 3], [3]),
([1, 2], [2, 3], [1]),
([1, 2], [2, 3], [2]),
([1, 2], [3], [1]),
([1, 2], [3], [2]),
([2, 3], [3], [1]),
([2, 3], [1], [2]),
([3], [1], [2]),
([1, 2], [2, 3], [3], [1]),
([1, 2], [2, 3], [3], [2]),
([1, 2], [2, 3], [1], [2]),
([1, 2], [3], [1], [2]),
([2, 3], [3], [1], [2]),
([1, 2], [2, 3], [3], [1], [2])]
If you want no duplicate elements in the resulting subsets, use this instead:
>>> filter(lambda s: sorted(sum(s,[])) == sorted(lis1), powerset(lis2))
[([1, 2], [3]), ([2, 3], [1]), ([3], [1], [2])]
Both methods use sum(s, []) to flatten the nested lists and then compare those to the original elements using either set (all present, ignore duplicates) or sorted (all present, exact same count).