2

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

Anurag Sharma
  • 4,839
  • 13
  • 59
  • 101
  • "one such combination is `[[1,2],[2,3]]` (all items of `lis1` i.e `[1,2]` is present in it)" -- what do you mean? It's missing `3`, which is present in `lis1`. – Patrick Collins Jul 28 '14 at 09:33
  • So, the list of lists can contain duplicate elements? What about duplicate subsets? Would `[[1,2],[3],[1,2]]` be allowed or not? Also, does the order matter? – tobias_k Jul 28 '14 at 09:57
  • @tobias_k duplicate elements are not allowed and order does not matter – Anurag Sharma Jul 28 '14 at 10:11
  • 1
    Duplicates as sublist are not allowed [1,2] is not equals [2,3]-- but 2 is contained in both [1,2] and [2,3]. Your example above is [[1,2],[3],[1,2]] is not allowed because it has 2 sub-list [1,2] and [1,2] which are equal. Also this is not a valid eg [[1,2],[3],[2,1]] (as order does not matter so [1,2],[2,1] are treated as equal and these cases will never exits in lis2 above) – Anurag Sharma Jul 28 '14 at 10:18
  • Whops, sorry, I was already writing an answer and totally forgot what I was asking about in the comment. Sorry for the confusion. – tobias_k Jul 28 '14 at 10:20
  • why are you including combinations of length 1? – Padraic Cunningham Jul 28 '14 at 10:29

1 Answers1

1

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

tobias_k
  • 81,265
  • 12
  • 120
  • 179
  • I have to get combinations of lis2 not lis1. If going by above procedure I have to make an extra check that sub-items(individual items returned by single row) returned by filter function must also match items in lis2. – Anurag Sharma Jul 28 '14 at 11:10
  • @AnuragSharma I edited my answer to better fit to your question. – tobias_k Jul 28 '14 at 11:20