Mdthbs

Given a list of 3-tuples, for example:[(1,2,3), (4,5,6), (7,8,9)] how would you compute all possible combinations and combinations of subsets?

In this case the result should look like this:

[
(1), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,4,7), (1,4,8), (1,4,9), (1,5,7), (1,5,8), (1,5,9), (1,6,7), (1,6,8), (1,6,9),
(2), ...,
(3), ...,
(4), (4,7), (4,8), (4,9),
(5), (5,7), (5,8), (5,9),
(6), (6,7), (6,8), (6,9),
(7), (8), (9)
]

• all tuples with identical elements are regarded the same


• combinations which derive from the same tuples are not allowed (e.g. these shouldn't be in the solution: (1,2), (4,6) or (7,8,9))

You can use recursion with a generator:

data = [(1,2,3), (4,5,6), (7,8,9)]

def combos(d, c = []):

   if len(c) == len(d):

     yield c

   else:

     for i in d:

        if i not in c:

           yield from combos(d, c+[i])



def product(d, c = []):

  if c:

    yield tuple(c)

  if d:

    for i in d[0]:

      yield from product(d[1:], c+[i])



result = sorted({i for b in combos(data) for i in product(b)})

final_result = [a for i, a in enumerate(result) if all(len(c) != len(a) or len(set(c)&set(a)) != len(a) for c in result[:i])]

Output:

[(1,), (1, 4), (1, 4, 7), (1, 4, 8), (1, 4, 9), (1, 5), (1, 5, 7), (1, 5, 8), (1, 5, 9), (1, 6), (1, 6, 7), (1, 6, 8), (1, 6, 9), (1, 7), (1, 8), (1, 9), (2,), (2, 4), (2, 4, 7), (2, 4, 8), (2, 4, 9), (2, 5), (2, 5, 7), (2, 5, 8), (2, 5, 9), (2, 6), (2, 6, 7), (2, 6, 8), (2, 6, 9), (2, 7), (2, 8), (2, 9), (3,), (3, 4), (3, 4, 7), (3, 4, 8), (3, 4, 9), (3, 5), (3, 5, 7), (3, 5, 8), (3, 5, 9), (3, 6), (3, 6, 7), (3, 6, 8), (3, 6, 9), (3, 7), (3, 8), (3, 9), (4,), (4, 7), (4, 8), (4, 9), (5,), (5, 7), (5, 8), (5, 9), (6,), (6, 7), (6, 8), (6, 9), (7,), (8,), (9,)]

Using itertools:

import itertools as it



def all_combinations(groups):

    result = set()

    for prod in it.product(*groups):

        for length in range(1, len(groups) + 1): 

            result.update(it.combinations(prod, length))

    return result



all_combinations([(1,2,3), (4,5,6), (7,8,9)])

Here is a non-recursive solution with a simple for loop. Uniqueness if enforced by applying set to the list of output tuples.

lsts = [(1,2,3), (4,5,6), (7,8,9)]



res = [[]]

for lst in lsts:

    res += [(*r, x) for r in res for x in lst]



# print({tuple(lst) for lst in res[1:]})

# {(5, 9), (4, 7), (6, 9), (1, 4, 7), (2, 6, 9), (4, 8), (3, 4, 7), (2,

# 8), (2, 6, 8), (9,), (2, 5, 8), (1, 6), (3, 6, 8), (2, 5, 9), (3, 5,

# 9), (3, 7), (2, 5), (3, 6, 9), (5, 8), (1, 6, 8), (3, 5, 8), (2, 6,

# 7), (4, 9), (6, 7), (1,), (2, 9), (1, 6, 9), (3,), (1, 5), (5,), (3,

# 6), (7,), (3, 6, 7), (1, 5, 9), (2, 6), (2, 4, 7), (1, 5, 8), (3, 4,

# 8), (8,), (3, 4, 9), (1, 4), (1, 6, 7), (3, 9), (1, 9), (2, 5, 7), (3,

# 5), (2, 7), (2, 4, 9), (6, 8), (1, 5, 7), (2,), (2, 4, 8), (5, 7), (1,

# 4, 8), (3, 5, 7), (4,), (3, 8), (1, 8), (1, 4, 9), (6,), (1, 7), (3,

# 4), (2, 4)}

Another version:

from itertools import product



lst = [(1,2,3), (4,5,6), (7,8,9)]



def generate(lst):

    for idx in range(len(lst)):

        for val in lst[idx]:

            yield (val,)

            for i in range(len(lst), idx+1, -1):

                l = tuple((val,) + i for i in product(*lst[idx+1:i]))

                if len(l) > 1:

                    yield from l



l = [*generate(lst)]

print(l)

Prints:

[(1,), (1, 4), (1, 5), (1, 6), (1, 4, 7), (1, 4, 8), (1, 4, 9), (1, 5, 7), (1, 5, 8), (1, 5, 9), (1, 6, 7), (1, 6, 8), (1, 6, 9), (2,), (2, 4), (2, 5), (2, 6), (2, 4, 7), (2, 4, 8), (2, 4, 9), (2, 5, 7), (2, 5, 8), (2, 5, 9), (2, 6, 7), (2, 6, 8), (2, 6, 9), (3,), (3, 4), (3, 5), (3, 6), (3, 4, 7), (3, 4, 8), (3, 4, 9), (3, 5, 7), (3, 5, 8), (3, 5, 9), (3, 6, 7), (3, 6, 8), (3, 6, 9), (4,), (4, 7), (4, 8), (4, 9), (5,), (5, 7), (5, 8), (5, 9), (6,), (6, 7), (6, 8), (6, 9), (7,), (8,), (9,)]

Oookay, although I don't fully understand the second rule, here is some short solution to the problem

from itertools import chain, combinations

blubb = [(1,2,3), (4,5,6), (7,8,9)]

blubb_as_set = list(map(set, blubb))



all_blubbs = list(chain.from_iterable(blubb))

all_blubb_combos = (combinations(all_blubbs, i) for i in range(1, 4))

as_a_list = list(chain.from_iterable(all_blubb_combos))



test_subset = lambda x: not any(set(x).issubset(blubb_set) for blubb_set in blubb_as_set)

list(filter(test_subset, as_a_list))

# alternative that includes single elements

list(filter(test_subset, as_a_list)) + list(map(lambda x: (x, ), chain.from_iterable(blubb)))

For the most parts you can leave out list calls.
Your can also create different not_allowed cases based on r if you need to deal with tuple's length more than 3.

Edit: explicit test for subset.