Поиск перекрывающихся списков в списке списков - PullRequest
Новая
       32

Поиск перекрывающихся списков в списке списков

1 голос
/ 27 марта 2019

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

Я рассмотрел обход в ширину, чтобы сделать это, но из-за того, как устроен список списков, трудно реализовать обход

Пример списка списков: 

input: 
[
 [1,2,3],
 [2,4,5],
 [4,6,8],
 [9,10,16],
 [16,18,19],
 [20,21,22]
]

output: [[1,2,3,4,5,6,8], [9,10,16,18,19], [20,21,22]]

Первые три списка должны быть объединены в один список (первый список и второй список имеют общий ресурс 2, второй и третий списки 4), четвертый и пятый должны быть объединены, поскольку эти два ресурса 16. Третий является не объединены ни с одним другим списком, так как он не разделяет ни один элемент с другими.

Хотя это можно сделать за O (n ^ 2) раз (n - количество списков), я пытаюсь найти наиболее эффективный из возможных способов.

Ответы [ 2 ]

1 голос
/ 28 марта 2019

Ваши внутренние списки не имеют повторяющихся элементов. Если это общий случай, то задача set comsolidation в Rosetta Code имеет решение Python, которое будет работать.

1 голос
/ 27 марта 2019

Вы можете сделать это в O (N * log N), где N - общее количество элементов во всех списках.

Идея проста с использованием структуры данных Union Find:

  1. Сначала давайте создадим N непересекающихся наборов для каждого уникального элемента на входе
  2. Объединить непересекающиеся множества для всех соседних элементов для каждого списка
  3. Соберите результат из непересекающихся множеств

Пример кода: 

def Find(id,P):
    if P[id]<0 : return id
    P[id]=Find(P[id],P)
    return P[id]

def Union(id1, id2, p):
    id1 = Find(id1,P)
    id2 = Find(id2,P)
    if id1 != id2:
        P[id2]=id1

input=[
 [1,2,3],
 [2,4,5],
 [4,6,8],
 [9,10,16],
 [16,18,19],
 [20,21,22]
]

P = {}

for list in input :
    for item in list :
        P[item] = -1

for list in input :
    for i in range(1,len(list)):
            Union(list[i-1], list[i], P)

ans = {}
for list in input :
    for item in list :
        if Find(item,P) not in ans:
            ans[Find(item,P)] = []
        ans[Find(item,P)].append(item)

ans = [set(x) for x in ans.values()]
print(ans)
...