Как кластеризовать списки с общими элементами

Question

Это проблема, которую я не могу найти в Leetcode или StackOverflow. Допустим, у вас есть набор списков номеров или ссылок следующим образом:

[[1,2,3],[3,4,5],[6,7,8],[8,9],[10],[7]]

Какой самый быстрый алгоритм объединения этих списков так, чтобы вывод был:

[[1,2,3,4,5],[6,7,8,9],[10]]

Большое спасибо.

Answer 1

RosettaCode имеет задачу установить консолидацию , в которой есть пример Python, который можно изменить для работы со списками:

def consolidate(lists):
    setlist = [set(lst) for lst in lists if lst]
    for i, s1 in enumerate(setlist):
        if s1:
            for s2 in setlist[i+1:]:
                intersection = s1.intersection(s2)
                if intersection:
                    s2.update(s1)
                    s1.clear()
                    s1 = s2
    return sorted(sorted(s) for s in setlist if s)

print(consolidate([[1,2,3],[3,4,5],[6,7,8],[8,9],[10],[7]]))

Выход:

[[1, 2, 3, 4, 5], [6, 7, 8, 9], [10]]

Answer 2

Это на самом деле не проблема кластеризации, а проблема множества union .

По именам " union find " или " disjoint-set " вы можете найти некоторые хорошо обсужденные подходы, чтобы сделать эти вещи быстрыми.

Answer 3

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

Каждый список порождает ненаправленные ребра, которые соединяли первый элемент с другими, например,

[1,2,3] -> [(1,2), (1,3)]
[3,4,5] -> [(3,4), (3,5)]
[6,7,8] -> [(6,7), (6,8)]
[8,9]   -> [(8,9)]
[10]    -> []
[7]     -> []

Затем выполните поиск в глубину, чтобы найти подключенные компоненты. В Python все идет примерно так.

import collections
def merge(lsts):
    neighbors = collections.defaultdict(set)
    for lst in lsts:
        if not lst:
            continue
        for x in lst:
            neighbors[x].add(lst[0])
            neighbors[lst[0]].add(x)
    visited = set()
    for v in neighbors:
        if v in visited:
            continue
        stack = [v]
        component = []
        while stack:
            w = stack.pop()
            if w in visited:
                continue
            visited.add(w)
            component.append(w)
            stack.extend(neighbors[w])
        yield component