在lis中找到所有的钥匙

Question

我有一个“组合”问题，需要找到一组不同的密钥，我试图找到一个优化的解决方案：

我有一个列表“l”：

l = [[1, 5],
 [5, 7],
 [4, 9],
 [7, 9],
 [50, 90],
 [100, 200],
 [90, 100],
 [2, 90],
 [7, 50],
 [9, 21],
 [5, 10],
 [8, 17],
 [11, 15],
 [3, 11]]

每个Id都链接到另一个Id，但也可能通过另一个键链接到另一个键（见下图）。目标是以优化的方式找到属于同一集群的所有密钥

结果是：

[{1, 2, 4, 5, 7, 9, 10, 21, 50, 90, 100, 200}, {8, 17}, {3, 11, 15}]

我现在的代码是：

out = []

while len(l)>0:
    first, *rest = l
    first = set(first)

    lf = -1
    while len(first)>lf:
        lf = len(first)
        print(lf)
        rest2 = []
        for r in rest:
            if len(first.intersection(set(r)))>0:
                first |= set(r)
            else:
                rest2.append(r)     
        rest = rest2

    out.append(first)
    l = rest

我得到了之前显示的结果。当在200万条线路上使用它时，问题就出现了，而这些线路需要很长时间才能运行。你知道吗

有没有其他优化方法来解决这个问题？你知道吗

Answer 1

您可以将其视为在图形中查找connected components的问题：

l = [[1, 5], [5, 7], [4, 9], [7, 9], [50, 90], [100, 200], [90, 100],
     [2, 90], [7, 50], [9, 21], [5, 10], [8, 17], [11, 15], [3, 11]]
# Make graph-like dict
graph = {}
for i1, i2 in l:
    graph.setdefault(i1, set()).add(i2)
    graph.setdefault(i2, set()).add(i1)
# Find clusters
clusters = []
for start, ends in graph.items():
    # If vertex is already in a cluster skip
    if any(start in cluster for cluster in clusters):
        continue
    # Cluster set
    cluster = {start}
    # Process neighbors transitively
    queue = list(ends)
    while queue:
        v = queue.pop()
        # If vertex is new
        if v not in cluster:
            # Add it to cluster and put neighbors in queue
            cluster.add(v)
            queue.extend(graph[v])
    # Save cluster
    clusters.append(cluster)
print(*clusters)
# {1, 2, 100, 5, 4, 7, 200, 9, 10, 50, 21, 90} {8, 17} {3, 11, 15}

Answer 2

这是union-find algorithm / disjoint set data structure的典型用例。在Python库AFAIK中没有实现，但是我总是倾向于在附近有一个实现，因为它非常有用。。。你知道吗

l = [[1, 5], [5, 7], [4, 9], [7, 9], [50, 90], [100, 200], [90, 100],
 [2, 90], [7, 50], [9, 21], [5, 10], [8, 17], [11, 15], [3, 11]]

from collections import defaultdict
leaders = defaultdict(lambda: None)

def find(x):
    l = leaders[x]
    if l is not None:
        leaders[x] = find(l)
        return leaders[x]
    return x

# union all elements that transitively belong together
for a, b in l:
    leaders[find(a)] = find(b)

# get groups of elements with the same leader
groups = defaultdict(set)
for x in leaders:
    groups[find(x)].add(x)
print(*groups.values())
# {1, 2, 4, 5, 100, 7, 200, 9, 10, 50, 21, 90} {8, 17} {3, 11, 15}

对于n个节点，这种方法的运行时复杂度应该是O（nlogn），每次都需要logn步骤才能到达（并更新）leader。你知道吗