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

#python #algorithm #computer-science #graph-algorithm

#python #алгоритм #информатика #граф-алгоритм

Вопрос:

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

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

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

 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 — количество списков), я пытаюсь найти наиболее эффективный из возможных способов.

1. Всегда ли сортируются внутренние списки ([1,2,3])? Есть ли какие-либо другие ограничения / правила, о которых нам нужно знать?

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

3. «Сложно реализовать обход» вы хотите сказать, что не ищете решения с графиками или что вы принимаете их, но еще не нашли простого решения?

4. Можно ли рассматривать эти внутренние списки как наборы? Похоже, что у них нет повторений, и существует код для выполнения этого с помощью наборов.

5. Да, повторений нет

Ответ №1:

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

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

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

Пример кода:

 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)

Ответ №2:

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