I'm not sure if I found the most elegant way, but I think it solves your task.
L1 = [ [1,2], [2,6], [5,7], [1,6], [3,6], [2,3], [7,9], [6,7] ]
l1 = list(map(tuple, L1))
groups=set()
used = set()
#find groups:
for combi in itertools.combinations(l1,3):
t1, t2, t3 = combi
union = set(t1) | set(t2) | set(t3)
if len(union) == 3:
groups.add(tuple(union))
used.update([t1,t2,t3])
print(groups)
# {(1, 2, 6), (2, 3, 6)}
print(used)
# {(1, 2), (2, 3), (2, 6), (3, 6), (1, 6)}
#add tuples which are not in the groups:
result = list(groups) + [tup for tup in l1 if tup not in used]
print(result)
[(1, 2, 6), (2, 3, 6), (5, 7), (7, 9), (6, 7)]
If you are searching for bigger chain / unknown length chains then this one works aswell. As in the comments already discussed, if data gets big the performance is probably suboptimal.
import itertools
from collections import Counter
#changed the input a bit for debugging reasons
L1 = [ [1,2], [2,5], [5,7], [7,8], [8,1], [5,4], [4,3], [3,7], [1,6], [5,6], [1,9] ]
l1 = list(map(tuple, L1))
len_chain_min = 3 # choose shortest valid chain
len_chain_max = 8 # choose highest valid chain
groups=set()
used = set()
#find groups:
for chains in range(len_chain_min, len_chain_max+1):
for combi in itertools.combinations(l1,chains):
combi_sets = list(map(set, [*combi]))
union = set.union(*combi_sets)
each_number_occurences = Counter((num for tupl in combi for num in tupl))
# chain is only valid if every number never occurs more than twice, no brnaches aloud
if (len(union) == chains) and (each_number_occurences.most_common(1)[0][1] <= 2):
groups.add(tuple(union))
used.update([*combi])
print(f"number of tuples: {chains}\nunion group: {tuple(union)}\nused tuples for this group: {combi_sets}\n")
# add tuples which are not in the groups:
result = sorted(list(groups),key=len) + [tupl for tupl in l1 if tupl not in used]
print(f"{result=}")
Output:
number of tuples: 4
union group: (1, 2, 5, 6)
used tuples for this group: [{1, 2}, {2, 5}, {1, 6}, {5, 6}]
number of tuples: 4
union group: (3, 4, 5, 7)
used tuples for this group: [{5, 7}, {4, 5}, {3, 4}, {3, 7}]
number of tuples: 5
union group: (1, 2, 5, 7, 8)
used tuples for this group: [{1, 2}, {2, 5}, {5, 7}, {8, 7}, {8, 1}]
number of tuples: 5
union group: (1, 5, 6, 7, 8)
used tuples for this group: [{5, 7}, {8, 7}, {8, 1}, {1, 6}, {5, 6}]
number of tuples: 7
union group: (1, 2, 3, 4, 5, 7, 8)
used tuples for this group: [{1, 2}, {2, 5}, {8, 7}, {8, 1}, {4, 5}, {3, 4}, {3, 7}]
number of tuples: 7
union group: (1, 3, 4, 5, 6, 7, 8)
used tuples for this group: [{8, 7}, {8, 1}, {4, 5}, {3, 4}, {3, 7}, {1, 6}, {5, 6}]
result=[(1, 2, 5, 6), (3, 4, 5, 7), (1, 5, 6, 7, 8), (1, 2, 5, 7, 8), (1, 2, 3, 4, 5, 7, 8), (1, 3, 4, 5, 6, 7, 8), (1, 9)]
