Merging tuples on common items

def count_elems(items): counts = {} for tup in items: for el in tup: if not el in counts: counts[el] = 0 counts[el] += 1 return counts def merge_nonunique(items, counts): # Merge all subsets containing the repeated item (recursively) nonuniques = [] for item, count in counts.items(): if count > 1: s = set() for tup in items: if item in tup: s |= set(tup) ts = tuple(sorted(s)) if ts not in nonuniques: nonuniques.append(ts) if len(items) == len(nonuniques): return nonuniques return merge_nonunique(nonuniques, counts) def merge_unique(items, counts): # Get all subsets with unique items uniques = [] for tup in items: tup_len = len(tup) found_unique = 0 for item in tup: if counts[item] == 1: found_unique += 1 if tup_len == found_unique: uniques.append(tuple(sorted(tup))) return uniques def merge(items): counts = count_elems(items) nonuniques = merge_nonunique(items, counts) uniques = merge_unique(items, counts) return sorted(nonuniques + uniques) items = [(2,7), (3,11), (15,17), (10,14), (13,4), (6,18), (7,11), (8,9), (1,7), (4,5), (6,12)] items_len = len(items) from time import perf_counter s = perf_counter() print(merge(items)) # [(1, 2, 3, 7, 11), (4, 5, 13), (6, 12, 18), (8, 9), (10, 14), (15, 17)] e = perf_counter() print('Time: %.9f' % (e-s)) # 0.000383788 items = [(7,6), (12,4), (5,6,8), (3,2), (2,13), (14,5,7), (11,3,1)] print(merge(items)) # [(1, 2, 3, 11, 13), (4, 12), (5, 6, 7, 8, 14)] s = perf_counter() items = [('Finnland', 'Sweden'), ('Norway', 'Sweden'), ('United Kingdom', 'Ireland'), ('Romania', 'Bulgaria'), ('Poland', 'Czechia'), ('Poland', 'Belarus'), ('Denmark', 'Germany'), ('Austria', 'Czechia'), ('Slovakia', 'Hungary'), ('France', 'Spain'), ('Portugal', 'Spain'), ('Italy', 'France'), ('Estonia', 'Latvia'), ('Latvia', 'Lithuania'), ('Germany', 'Poland'), ('Hungary', 'Romania')] print(merge(items)) # [('Austria', 'Belarus', 'Czechia', 'Denmark', 'Germany', 'Poland'), ('Bulgaria', 'Hungary', 'Romania', 'Slovakia'), ('Estonia', 'Latvia', 'Lithuania'), ('Finnland', 'Norway', 'Sweden'), ('France', 'Italy', 'Portugal', 'Spain'), ('Ireland', 'United Kingdom')] e = perf_counter() print('Time: %.9f' % (e-s)) # Time: 0.000536465 items = [('Susan', 'Victor', 'Jeanette'), ('Anette', 'Claudia'), ('Trevor', 'Peter'), ('Gregory', 'Yvonne'), ('Wendy', 'Victoria'), ('Susan', 'Ernesto'), ('Daniel', 'Helen'), ('Daniel', 'Claudia'), ('John', 'Peter'), ('Melody', 'Jerome'), ('Claudio', 'Benoit'), ('Ben', 'Florian'), ('Florian', 'Trevor'), ('Ernesto', 'Greg'), ('Melody', 'Elaine'), ('Chris', 'Fabiano'), ('Fabiano', 'Claudio'), ('Victoria', 'Yvonne')] print(merge(items)) # [('Anette', 'Claudia', 'Daniel', 'Helen'), ('Ben', 'Florian', 'John', 'Peter', 'Trevor'), ('Benoit', 'Chris', 'Claudio', 'Fabiano'), ('Elaine', 'Jerome', 'Melody'), ('Ernesto', 'Greg', 'Jeanette', 'Susan', 'Victor'), ('Gregory', 'Victoria', 'Wendy', 'Yvonne')]