Styjun

Say I have for example the following nested list:

L = [['John','Sayyed'], ['John' , 'Simon'] ,['bush','trump'],
 ['Sam','Suri','NewYork'],['Suri','Orlando','Canada']]

How can I group these sublists, by getting the union of sublists which have a common element with at least another sublist within the group? So for the previous example the result should be:

[['John','Sayyed','Simon'] ,['bush','trump'],
 ['Sam','Suri','NewYork','Orlando','Canada']]

Thus the first two sublists are joined as they share 'John'.
Could someone please share their valuable thoughts ?

You can use networkx for that. 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:

import networkx as nx 

L = [['John','Sayyed'], ['John' , 'Simon'] ,['bush','trump']

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

['John', 'Sayyed', 'Simon', 'bush', 'trump']

Update

In the case of having sublists with more than 2 elements, you can get all the length 2 combinations from each sublist and use these as the network edges:

from itertools import combinations, chain

L = [['John','Sayyed'], [ 'John' , 'Simon'] ,['bush','trump'],
 ['Sam','Suri','NewYork'],['Suri','Orlando','Canada']]

L2_nested = [list(combinations(l,2)) for l in L]
L2 = list(chain.from_iterable(L2_nested))
#[('John', 'Sayyed'), ('John', 'Simon'), ('bush', 'trump'), ('Sam', 'Suri')...

G=nx.Graph()
G.add_edges_from(L2)
list(nx.connected_components(G))

['John', 'Sayyed', 'Simon',
'bush', 'trump',
'Canada', 'NewYork', 'Orlando', 'Sam', 'Suri']

Networkx also allows you to visualize the network with nx.draw:

pos = nx.spring_layout(G, scale=20)
nx.draw(G, pos, node_color='lightblue', node_size=500, with_labels=True)

Details

More detailed explanation on connected components:

In graph theory, a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph

So essentially, this code creates a graph, with edges from the list, where each edge is composed by two values u,v where u and v will be nodes connected by this edge.

And hence, the union of sublists with at least one sublist with a common element can be translated into a Graph Theory problem as all nodes that are reachable between each other through the existing paths.

If order is important and the list are large, you can use this two pronged method:

 l = [['john', 'sayyid'], ['john', 'simon'], ['b', 't']]

 def join(l1, l2):
 mset = set(l1)
 result = l1[:] # deep copy
 for each in l2:
 if each in mset:
 continue
 else:
 result.append(each)
 return result

To merge within the master list, you can just call the list by their rank and pop the original list:

l1 = l.pop(0)
l2 = l.pop(0)
l.insert(0, join(l1, l2))
>>> l:
[['john', 'sayyid', 'simon'], ['b', 't']]

To merge 2 lists:

merge = lambda l1, l2: l1 + [ x for x in l2 if x not in l1 ]

To be more efficient, create a set on l1;

A simple approach

L = [['John','Sayyed'], [ 'John' , 'Simon'] ,['bush','trump']]
L[0].extend([x for x in L[1] if x not in L[0]])
L.pop(1)
print(L) 

See

List Comprehensions

Append vs Extend