基于共享值的列表的群集列表

Question

我有一个列表列表，其中每个子列表包含一些整数：

o = [[1,2],[3,4],[2,3],[5,4]]

我想创建一个新的列表列表，在这个列表中，o中共享一个公共成员的任何两个子列表都将被合并。这个合并过程应该持续到没有两个子列表共享一个公共元素为止。给定o，我们将[1,2]与{}合并，因为它们共享一个2，然后我们将该组与{}合并，因为[1,2,3]和{}都包含一个3，依此类推。在

集群o的预期输出是[[1,2,3,4,5]]

我有一个预感，有一个方法，这是远远优于我目前的方法（见下文）。如果其他人能就如何最有效地（在时间上，然后在空间上）完成这项任务提出任何建议，我们将不胜感激。在

^{pr2}$

Answer 1

from collections import deque

o = [[1,2],[3,4],[2,3],[5,4], [10, 11, 12], [13, 15], [4,6], [6, 8], [23,25]]

o = sorted(o, key=lambda x:min(x))
queue = deque(o)

grouped = []
while len(queue) >= 2:
    l1 = queue.popleft()
    l2 = queue.popleft()
    s1 = set(l1)
    s2 = set(l2)

    if s1 & s2:
        queue.appendleft(s1 | s2)
    else:
        grouped.append(s1)
        queue.appendleft(s2)
#         print(set(l1).union(set(l2)))
if queue:
    grouped.append(queue.pop())

print(grouped)

输出

^{pr2}$

Answer 2

可以使用递归：

def cluster(d, current = []):
  options = [i for i in d if any(c in current for c in i)]
  _flattened = [i for b in options for i in b]
  d = list(filter(lambda x:x not in options, d))
  if not options or not d:
    yield current+_flattened
  if d and not options:
    yield from cluster(d[1:], d[0])
  elif d:
    yield from cluster(d, current+_flattened)

for a, *b in [[[1,2],[6,4],[2,3],[5,4]], [[1,2],[3,4],[2,3],[5,4]], [[1,2],[3,4],[2,3],[5,4], [10, 11, 12], [13, 15], [4,6], [6, 8], [23,25]]]:
  print([list(set(i)) for i in cluster(b, a)])

输出：

^{pr2}$