Find in python combinations of mutually exclusive sets from a list's elements

Question

In a project I am currently working on I have implemented about 80% of what I want my program to do and I am very happy with the results.

In the remaining 20% I am faced with a problem which puzzles me a bit on how to solve. Here it is:

I have come up with a list of lists which contain several numbers (arbitrary length) For example:

listElement[0] = [1, 2, 3]
listElement[1] = [3, 6, 8]
listElement[2] = [4, 9]
listElement[4] = [6, 11]
listElement[n] = [x, y, z...]

where n could reach up to 40,000 or so.

Assuming each list element is a set of numbers (in the mathematical sense), what I would like to do is to derive all the combinations of mutually exclusive sets; that is, like the powerset of the above list elements, but with all non-disjoint-set elements excluded.

So, to continue the example with n=4, I would like to come up with a list that has the following combinations:

newlistElement[0] = [1, 2, 3]
newlistElement[1] = [3, 6, 8]
newlistElement[2] = [4, 9]
newlistElement[4] = [6, 11] 
newlistElement[5] = [[1, 2, 3], [4, 9]]
newlistElement[6] = [[1, 2, 3], [6, 11]]
newlistElement[7] = [[1, 2, 3], [4, 9], [6, 11]]
newlistElement[8] = [[3, 6, 8], [4, 9]]
newlistElement[9] = [[4, 9], [6, 11]

An invalid case, for example would be combination [[1, 2, 3], [3, 6, 8]] because 3 is common in two elements. Is there any elegant way to do this? I would be extremely grateful for any feedback.

I must also specify that I would not like to do the powerset function, because the initial list could have quite a large number of elements (as I said n could go up to 40000), and taking the powerset with so many elements would never finish.

Answer 1

I'd use a generator:

import itertools

def comb(seq):
   for n in range(1, len(seq)):
      for c in itertools.combinations(seq, n): # all combinations of length n
         if len(set.union(*map(set, c))) == sum(len(s) for s in c): # pairwise disjoint?
            yield list(c)

for c in comb([[1, 2, 3], [3, 6, 8], [4, 9], [6, 11]]):
   print c

This produces:

[[1, 2, 3]]
[[3, 6, 8]]
[[4, 9]]
[[6, 11]]
[[1, 2, 3], [4, 9]]
[[1, 2, 3], [6, 11]]
[[3, 6, 8], [4, 9]]
[[4, 9], [6, 11]]
[[1, 2, 3], [4, 9], [6, 11]]

If you need to store the results in a single list:

print list(comb([[1, 2, 3], [3, 6, 8], [4, 9], [6, 11]]))