Check if two lists in list have common elements. Connect them if so, without duplicates

Question

I am stuck on how to solve this problem.

Given a set of lists in a list, if any two sets of lists contain a common element, the two lists would be combined into one.

Suppose I have a set of lists in a list [[0, 1], [3, 6], [3, 9]]. Notice that [3, 6] and [3, 9] have a common element 3, so they are combined into [3, 6, 9], so how to convert this set of lists in a list into [[0,1], [3, 6, 9]]?

This is my current code but I am stuck.

for i in connected:
    for j in connected:
        a_set = set(i)
        b_set = set(j)
        if (a_set & b_set):
            i.extend(j)
            connected.remove(j)
    

Answer 1

Challenging! This is my approach:

def combine_commons(input: list) -> list:
    combine_found = False
    for ct_current, item_current in enumerate(input):
        
        # try to find a element that shares item:
        combine_into = None
        for ct_search, item_search in enumerate(input):
            if ct_current==ct_search: continue # can skip if i==j
            if any(i in item_search for i in item_current):
                # if any elements match, combine them.
                combine_into = item_search
                combine_found = True
                break

        if isinstance(combine_into, list):
            input[ct_current] = list(set(item_current + combine_into)) # overwrite with new combined
            del input[ct_search]

    if combine_found: return combine_commons(input)
    return input

print(combine_commons([[0, 1], [3, 6], [3, 9]]))
print(combine_commons([[1,2],[2,3],[2,5],[5,1]]))
# >>> [[0, 1], [9, 3, 6]]
# >>> [[1, 2, 3, 5]]

What it basically does is it loops twice through the list of lists. Then, for each i and j it checks if they have something in common. If they do, combine them into one (overwriting element i with the new long list and deleting element j). This then breaks the loop, so my solution was to check all the items again (looking for mergers) in a recursive fashion. Hope this helps!

Answer 2

Sometimes using the right data structures can make all the difference. Your problem seems to require something like an adjacency matrix to resolve. So, here is a quick way to do this using Graphs. The intuition is as follows -

This is inspired by the approaches mentioned here. Here is the code which is using highly optimized inbuilt networkx functions.

import networkx as nx

def merge_lists(l):
    islands = nx.connected_components(nx.from_edgelist(l))
    return [list(i) for i in islands]

print(merge_lists([[0,1],[3,6],[3,9]]))
print(merge_lists([[1,2],[2,3],[2,5],[5,1]]))
print(merge_lists([[1,2],[2,3],[9,8],[5,6],[5,7]]))

[[0, 1], [9, 3, 6]]               #case 1, [[0,1],[3,6],[3,9]]

[[1, 2, 3, 5]]                    #case 2, [[1,2],[2,3],[2,5],[5,1]]

[[1, 2, 3], [8, 9], [5, 6, 7]]    #case 3, [[1,2],[2,3],[9,8],[5,6],[5,7]]

Any variations in the cases can be easily accommodated by modifying the graph created in the function.