Эту проблему я не могу найти в 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]]
Большое спасибо.
Подготовьте график из списков следующим образом и найдите связанные компоненты, используя поиск в глубину.
Каждый список порождает неориентированные ребра, которые соединяют первый элемент с другими, например,
[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
В 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]]
На самом деле это проблема кластеризации нет, но проблема набора союз.
По именам «союз найти» или «непересекающееся множество» вы можете найти несколько хорошо обсуждаемых подходов, чтобы сделать эти вещи быстрыми.