1

Im struggling with something that is probably not complicated. I have a list of lists and I want to Group the elements together if they share any common elements:

enter image description here

For example first list [1,2] is grouped with third list [3,4] because they "overlap" through second list [2,3]

There must be some easier way than:

a = [[1,2],
     [2,3],
     [3,4],
     [7,8]]

newlist = []
for count, pair in enumerate(a):
    if count==0:
        newlist.append(pair)
    else:
        for index, group in enumerate(newlist):
            if not set(group).isdisjoint(pair):
                newlist[index].extend(pair)
            else:
                newlist.append(pair)

newlist = [set(group) for group in newlist]

newlist
[{1, 2, 3, 4}, {8, 7}]
yatu
  • 86,083
  • 12
  • 84
  • 139
BERA
  • 1,345
  • 3
  • 16
  • 36

1 Answers1

2

Similarly to this post, a way to approach this is using networkx. Generate a graph, and add your list as the graph edges using add_edges_from. Then use connected_components, which will precisely give you a list of sets of the connected components in the graph:

L = [[1,2],
     [2,3],
     [3,4],
     [7,8]]

import networkx as nx

G=nx.Graph()
G.add_edges_from(L)
newlist  = list(nx.connected_components(G))

print(new_list)
# [{1, 2, 3, 4}, {7, 8}]
yatu
  • 86,083
  • 12
  • 84
  • 139
  • Nice! What if each list in the list of lists had 100 elements? Would using networkx still be possible? – BERA May 10 '19 at 15:56
  • 1
    Check how I approach this in the [dupe](https://stackoverflow.com/questions/53886120/union-of-sublists-with-common-elements), it is possible! @BERA – yatu May 10 '19 at 16:01