Python fusionner la liste multiple avec intersection [dupliquer]
possible Duplicate:
Python: fusion de liste simple basée sur des intersections
j'ai une liste multiple:
list=[[1,2,3],[3,5,6],[8,9,10],[11,12,13]]
Est-il intelligent et rapide façon d'obtenir toutes les sous-listes avec au moins une intersection. Dans mon exemple je veux que le code retourne
result=[[1,2,3,5,6],[8,9,10],[11,12,13]]
3 réponses
cela fonctionne, mais n'est peut-être pas très élégant:
def merge_lists(l):
s=map(set, l)
i, n=0, len(s)
while i < n-1:
for j in xrange(i+1, n):
if s[i].intersection(s[j]):
s[i].update(s[j])
del s[j]
n-=1
break
else:
i+=1
return [sorted(i) for i in s]
bonne question! C'est beaucoup plus simple si vous pensez à elle comme un-composants problème dans un graphe. Le code suivant utilise l'excellente fonction networkx et la fonction pairs de cette question .
def pairs(lst):
i = iter(lst)
first = prev = item = i.next()
for item in i:
yield prev, item
prev = item
yield item, first
lists = [[1,2,3],[3,5,6],[8,9,10],[11,12,13]]
import networkx
g = networkx.Graph()
for sub_list in lists:
for edge in pairs(sub_list):
g.add_edge(*edge)
networkx.connected_components(g)
[[1, 2, 3, 5, 6], [8, 9, 10], [11, 12, 13]]
explication
nous créons un nouveau graphique (vide) g . Pour chaque sous-liste dans lists , examiner ses éléments les noeuds du graphe et Ajouter un bord entre eux. (Puisque nous ne nous soucions que de la connexité, nous n'avons pas besoin d'ajouter tous les bords-seulement adjacents!) Notez que add_edge prend deux objets, les traite comme des noeuds (et les ajoute s'ils ne sont pas déjà là), et ajoute un bord entre eux.
alors, nous trouvons juste les composants connectés du graphe -- un problème résolu! -- et les sortir comme nos ensembles se croisent.
Vous pouvez le faire avec un seul passage à travers les données:
list_of_lists = [[1, 2, 3], [3, 5, 6], [8, 9, 10], [11, 12, 13]]
sets = {}
for lst in list_of_lists:
s = set(lst)
t = set()
for x in s:
if x in sets:
t.update(sets[x])
else:
sets[x] = s
for y in t:
sets[y] = s
s.update(t)
ids = set()
for s in sets.itervalues():
if id(s) not in ids:
ids.add(id(s))
print s
cela crée un dictionnaire sets cartographiant chaque élément à l'ensemble auquel il appartient. Si un élément a déjà été vu, son ensemble est subsumé dans le fichier courant et toutes les entrées dictinaires correspondant au premier ensemble sont mises à jour.
Enfin, nous devons trouver tous les ensembles uniques dans les valeurs du dictionnaire sets . Notez que tandis que je mis en œuvre ceci comme un dictionnaire de sets, le code fonctionne aussi avec des listes au lieu de sets.