Python aggregate lists that share a common item

Question

I'm looking for a function to aggregate lists that have a common item. The specific example I had in mind was the following case:

inputs = [['a','b'], ['a','c'], ['b','d'], ['e','f'], ['g','h'], ['i','k'], ['k','l']]
aggregated_output = [['a','b','c','d'],['e','f'],['g','h'],['i','k','l']]

as you can see, all the lists that share a common item have been bunched together. The order of the lists or the items in the lists in the output does not matter.

This looks very similar to connectivity in a graph, namely (connected) components. — MisterMiyagi, Jun 12 '22 at 12:37
Does this answer your question? [Python connected components](https://stackoverflow.com/questions/10301000/python-connected-components) — MisterMiyagi, Jun 12 '22 at 12:40

I'mahdi · Accepted Answer · 2022-06-12T12:41:42.927

Maybe Brute-Force Solutions help you:

inputs = [['a','b'], ['a','c'], ['b','d'], ['e','f'], ['g','h'], ['i','k'], ['k','l']]

res = []
for arr in inputs:
    flaq = False
    for r in res:
        for a in arr:
            if a in r:
                r += [a for a in arr if not a in r]
                flaq = True
                break
    if not flaq:
        res.append(arr)
print(res)

Output:

[['a', 'b', 'c', 'd'], ['e', 'f'], ['g', 'h'], ['i', 'k', 'l']]

Sash Sinha · Answer 2 · 2022-06-12T16:45:50.783

2

You could use connected_components from the networkx package:

>>> import networkx as nx
>>> edges = [['a', 'b'], ['a', 'c'], ['b', 'd'], ['e', 'f'], ['g', 'h'], ['i', 'k'], ['k', 'l']]
>>> graph = nx.Graph()
>>> graph.add_edges_from(edges)
>>> [list(c) for c in nx.connected_components(graph)]
[['a', 'c', 'd', 'b'], ['f', 'e'], ['h', 'g'], ['k', 'i', 'l']]

edited Jun 12 '22 at 16:45

answered Jun 12 '22 at 12:41

Sash Sinha

18,743
3
23
40

Python aggregate lists that share a common item

2 Answers2