Союз сублистов с общими элементами

Question

Скажем, у меня есть, например, следующий вложенный список:

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

Как я могу сгруппировать эти подсписки, получив объединение подсписков, которые имеют общий элемент, по крайней мере, с другим подсписком в группе?Таким образом, для предыдущего примера результат должен быть:

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

Таким образом, первые два подсписка объединяются, поскольку они совместно используют 'John'.Может ли кто-нибудь поделиться своими ценными мыслями?

Answer 1

Простой подход

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) 

См.

Список понятий

Добавление и расширение

Answer 2

Если порядок важен и список большой, вы можете использовать этот два метода:

 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

Для объединения в основной список вы можете просто вызвать список с помощьюих рейтинг и поп первоначальный список:

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

Answer 3

Чтобы объединить 2 списка:

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

Для большей эффективности создайте set для l1;

Answer 4

nx.connected_components

Вы можете использовать networkx для этого.Создайте график и добавьте свой список в виде ребер графика, используя add_edges_from.Затем используйте connected_components, который точно даст вам список наборов подключенных компонентов на графике:

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'}]

---

Списки с несколькими элементами

В случае наличия подсписков с более чем 2 элементами, вы можете получить всю длину 2 combinations из каждого подсписка и использовать их в качестве границ сети:

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'}]

Мы также можем визуализировать эти подключенные компоненты с помощью nx.draw:

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

---

Подробности

Более подробное объяснение подключенных компонентов :

В теории графов подключенный компонент (или просто компонент) неориентированного графа - это подграф, в котором любые две вершины связаны друг с другом путями и который не связан ни с какими дополнительными вершинами в суперграфе

Таким образом, по сути, этот код создаетграфик с ребрами из списка, где каждое ребро состоит из двух значений u,v, где u и v будут узлами, соединенными этим ребром.

И, следовательно, объединение подсписков с хотя бы одним подсписком с общим элементом может быть переведено в задачу теории графов как все узлы, которые достижимы между собой по существующим путям.