Unique combinations of a list of tuples

Question

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

Answer 1

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,)]

Answer 2

Here is a non-recursive solution with a simple for loop. Uniqueness is enforced by applying set to the list of the outputted 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)}

Answer 3

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

Answer 4

Another version:

from itertools import product, combinations

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 j in range(1, len(lst)):
                for c in combinations(lst[idx+1:], j):
                    yield from tuple((val,) + i for i in product(*c))

l = [*generate(lst)]
print(l)

Prints:

[(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,), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (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, 7), (3, 8), (3, 9), (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,)]

Answer 5

Thank to @wovano for clarifying rule 2. This makes the solution even more shorter:

from itertools import chain, combinations, product

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

set_combos = chain.from_iterable(combinations(blubb, i) for i in range(len(blubb) + 1))
result_func = list(chain.from_iterable(map(lambda x: product(*x), set_combos)))

And as a bonus a speed comparison. @hilberts_drinking_problem's solution is awesome but there is an overhead.

def pure_python(list_of_tuples):
    res = [tuple()]
    for lst in list_of_tuples:
        res += [(*r, x) for r in res for x in lst]
    return res


def with_itertools(list_of_tuples):
    set_combos = chain.from_iterable(combinations(list_of_tuples, i) for i in range(len(list_of_tuples) + 1))
    return list(chain.from_iterable(map(lambda x: product(*x), set_combos)))


assert sorted(with_itertools(blubb), key=str) == sorted(pure_python(blubb), key=str)

Both computes the same stuff, but...

%timeit with_itertools(blubb)
7.18 µs ± 11.3 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%timeit pure_python(blubb)
10.5 µs ± 46 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

although for small samples itertools are little bit faster there is a large gap when the set grows:

import toolz
large_blubb = list(toolz.partition_all(3, range(3*10)))
assert sorted(with_itertools(large_blubb), key=str) == sorted(pure_python(large_blubb), key=str)

%timeit with_itertools(large_blubb)
106 ms ± 307 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit pure_python(large_blubb)
262 ms ± 1.85 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

which makes itertools's solution 2,5 times faster.

---

Edit: corrected according to rule 2. Plus speed comparison Edit: fix yet another mistake - now the speed comparison is realistic