Мой ввод - это список списков. Некоторые из них имеют общие элементы, например.
L = [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]
Мне нужно объединить все списки, которые разделяют общий элемент, и повторить эту процедуру, если больше нет списков с одним и тем же элементом. Я думал об использовании логических операций и цикла while, но не мог найти хорошего решения.
Конечный результат должен быть:
L = [['a','b','c','d','e','f','g','o','p'],['k']]
Вы можете видеть свой список как обозначение для графика, т.е. ['a','b','c'] - это граф с тремя узлами, связанными друг с другом. Проблема, которую вы пытаетесь решить, заключается в поиске связанных компонентов в этом графике.
Вы можете использовать NetworkX для этого, что имеет то преимущество, что он почти гарантированно корректен:
l = [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]
import networkx
from networkx.algorithms.components.connected import connected_components
def to_graph(l):
G = networkx.Graph()
for part in l:
# each sublist is a bunch of nodes
G.add_nodes_from(part)
# it also imlies a number of edges:
G.add_edges_from(to_edges(part))
return G
def to_edges(l):
"""
treat `l` as a Graph and returns it edges
to_edges(['a','b','c','d']) -> [(a,b), (b,c),(c,d)]
"""
it = iter(l)
last = next(it)
for current in it:
yield last, current
last = current
G = to_graph(l)
print connected_components(G)
# prints [['a', 'c', 'b', 'e', 'd', 'g', 'f', 'o', 'p'], ['k']]
Чтобы решить эту проблему самостоятельно, вам нужно преобразовать список во что-то графическое, так что вы можете также использовать networkX с самого начала.
Алгоритм:
Таким образом, вы можете использовать наборы вместо списка. Следующая программа должна это сделать.
l = [['a', 'b', 'c'], ['b', 'd', 'e'], ['k'], ['o', 'p'], ['e', 'f'], ['p', 'a'], ['d', 'g']]
out = []
while len(l)>0:
first, *rest = l
first = set(first)
lf = -1
while len(first)>lf:
lf = len(first)
rest2 = []
for r in rest:
if len(first.intersection(set(r)))>0:
first |= set(r)
else:
rest2.append(r)
rest = rest2
out.append(first)
l = rest
print(out)
Я столкнулся с той же проблемой, связанной с попыткой объединить списки с общими значениями. Этот пример может быть тем, что вы ищете. Он только перебирает списки один раз и обновляет набор результатов по мере его появления.
lists = [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]
lists = sorted([sorted(x) for x in lists]) #Sorts lists in place so you dont miss things. Trust me, needs to be done.
resultslist = [] #Create the empty result list.
if len(lists) >= 1: # If your list is empty then you dont need to do anything.
resultlist = [lists[0]] #Add the first item to your resultset
if len(lists) > 1: #If there is only one list in your list then you dont need to do anything.
for l in lists[1:]: #Loop through lists starting at list 1
listset = set(l) #Turn you list into a set
merged = False #Trigger
for index in range(len(resultlist)): #Use indexes of the list for speed.
rset = set(resultlist[index]) #Get list from you resultset as a set
if len(listset & rset) != 0: #If listset and rset have a common value then the len will be greater than 1
resultlist[index] = list(listset | rset) #Update the resultlist with the updated union of listset and rset
merged = True #Turn trigger to True
break #Because you found a match there is no need to continue the for loop.
if not merged: #If there was no match then add the list to the resultset, so it doesnt get left out.
resultlist.append(l)
print resultlist
resultset = [['a', 'b', 'c', 'd', 'e', 'g', 'f', 'o', 'p'], ['k']]
Я думаю, что это можно решить, моделируя проблему как graph. Каждый подсписок является node и разделяет ребро с другим node, только если два подписок имеют некоторый общий элемент. Таким образом, объединенный подсписок в основном представляет собой подключенный компонент на графике. Слияние всех из них - это просто поиск всех подключенных компонентов и их перечисление.
Это можно сделать простым прохождением по графику. Оба BFS и DFS могут быть использованы, но я используя DFS здесь, поскольку для меня он несколько короче.
l = [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]
taken=[False]*len(l)
l=map(set,l)
def dfs(node,index):
taken[index]=True
ret=node
for i,item in enumerate(l):
if not taken[i] and not ret.isdisjoint(item):
ret.update(dfs(item,i))
return ret
def merge_all():
ret=[]
for i,node in enumerate(l):
if not taken[i]:
ret.append(list(dfs(node,i)))
return ret
print merge_all()
Моя попытка. Функциональный взгляд на него.
#!/usr/bin/python
from collections import defaultdict
l = [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]
hashdict = defaultdict(int)
def hashit(x, y):
for i in y: x[i] += 1
return x
def merge(x, y):
sums = sum([hashdict[i] for i in y])
if sums > len(y):
x[0] = x[0].union(y)
else:
x[1] = x[1].union(y)
return x
hashdict = reduce(hashit, l, hashdict)
sets = reduce(merge, l, [set(),set()])
print [list(sets[0]), list(sets[1])]
Как Йохен Ритцел указал, вы ищете связанные компоненты на графике. Вот как вы могли реализовать его без использования библиотеки графов:
from collections import defaultdict
def connected_components(lists):
neighbors = defaultdict(set)
seen = set()
for each in lists:
for item in each:
neighbors[item].update(each)
def component(node, neighbors=neighbors, seen=seen, see=seen.add):
nodes = set([node])
next_node = nodes.pop
while nodes:
node = next_node()
see(node)
nodes |= neighbors[node] - seen
yield node
for node in neighbors:
if node not in seen:
yield sorted(component(node))
L = [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]
print list(connected_components(L))
Не зная, чего вы хотите, я решил просто предположить, что вы имели в виду: я хочу найти каждый элемент только один раз.
#!/usr/bin/python
def clink(l, acc):
for sub in l:
if sub.__class__ == list:
clink(sub, acc)
else:
acc[sub]=1
def clunk(l):
acc = {}
clink(l, acc)
print acc.keys()
l = [['a', 'b', 'c'], ['b', 'd', 'e'], ['k'], ['o', 'p'], ['e', 'f'], ['p', 'a'], ['d', 'g']]
clunk(l)
Результат выглядит так:
['a', 'c', 'b', 'e', 'd', 'g', 'f', 'k', 'o', 'p']
Это, пожалуй, более простой/быстрый алгоритм и, кажется, хорошо работает -
l = [['a', 'b', 'c'], ['b', 'd', 'e'], ['k'], ['o', 'p'], ['e', 'f'], ['p', 'a'], ['d', 'g']]
len_l = len(l)
i = 0
while i < (len_l - 1):
for j in range(i + 1, len_l):
# i,j iterate over all pairs of l elements including new
# elements from merged pairs. We use len_l because len(l)
# may change as we iterate
i_set = set(l[i])
j_set = set(l[j])
if len(i_set.intersection(j_set)) > 0:
# Remove these two from list
l.pop(j)
l.pop(i)
# Merge them and append to the orig. list
ij_union = list(i_set.union(j_set))
l.append(ij_union)
# len(l) has changed
len_l -= 1
# adjust 'i' because elements shifted
i -= 1
# abort inner loop, continue with next l[i]
break
i += 1
print l
# prints [['k'], ['a', 'c', 'b', 'e', 'd', 'g', 'f', 'o', 'p']]
Я нашел itertools быстрый вариант для слияния списков, и он решил эту проблему для меня:
import itertools
LL = set(itertools.chain.from_iterable(L))
# LL is {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'k', 'o', 'p'}
for each in LL:
components = [x for x in L if each in x]
for i in components:
L.remove(i)
L += [list(set(itertools.chain.from_iterable(components)))]
# then L = [['k'], ['a', 'c', 'b', 'e', 'd', 'g', 'f', 'o', 'p']]
Для больших наборов, сортирующих LL по частоте от наиболее распространенных элементов до минимума, можно немного ускорить процесс