Xjyuk

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.