Объединить списки, которые имеют общие элементы - PullRequest
Новая
       47

Объединить списки, которые имеют общие элементы

37 голосов
/ 30 января 2011

Мой ввод - это список списков. Некоторые из них имеют общие элементы, например. 

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

Ответы [ 13 ]

0 голосов
/ 28 декабря 2018

Я скучаю по не quirurgic версии. Я публикую это в 2018 году (7 лет спустя)

легкий и нестабильный подход:

1) сделать декартово произведение (перекрестное соединение), объединяющее оба общих элемента
2) удалить дупс 

#your list
l=[['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]

#import itertools
from itertools import product, groupby

#inner lists to sets (to list of sets)
l=[set(x) for x in l]

#cartesian product merging elements if some element in common
for a,b in product(l,l):
    if a.intersection( b ):
       a.update(b)
       b.update(a)

#back to list of lists
l = sorted( [sorted(list(x)) for x in l])

#remove dups
list(l for l,_ in groupby(l))

#result
[['a', 'b', 'c', 'd', 'e', 'f', 'g', 'o', 'p'], ['k']]
0 голосов
/ 05 октября 2013

Возможно, это более простой / быстрый алгоритм, и, похоже, он хорошо работает - 

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's 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']]
0 голосов
/ 30 января 2011

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

#!/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']
Страница:
...