Объединение списков, содержащих общие элементы

Ответ 1

Вы можете видеть свой список как обозначение для графика, т.е. ['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 с самого начала.

Ответ 2

Алгоритм:

• возьмите первый набор A из списка
• для каждого другого набора B в списке, если B имеет общий элемент с A join B в A; удалить B из списка
• повторить 2. пока не будет больше перекрываться с A
• положить A в outpup
• повторите 1. с остальным списком

Таким образом, вы можете использовать наборы вместо списка. Следующая программа должна это сделать.

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)

Ответ 3

Я столкнулся с той же проблемой, связанной с попыткой объединить списки с общими значениями. Этот пример может быть тем, что вы ищете. Он только перебирает списки один раз и обновляет набор результатов по мере его появления.

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

Ответ 4

Я думаю, что это можно решить, моделируя проблему как 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()

Ответ 5

Моя попытка. Функциональный взгляд на него.

#!/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])]

Ответ 6

Как Йохен Ритцел указал, вы ищете связанные компоненты на графике. Вот как вы могли реализовать его без использования библиотеки графов:

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))

Ответ 7

Не зная, чего вы хотите, я решил просто предположить, что вы имели в виду: я хочу найти каждый элемент только один раз.

#!/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']

Ответ 8

Это, пожалуй, более простой/быстрый алгоритм и, кажется, хорошо работает -

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

Ответ 9

Я нашел 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 по частоте от наиболее распространенных элементов до минимума, можно немного ускорить процесс