如何根据共享项目有效地对对进行分组？

Question

我有一个对（元组）的列表，为了简化，如下所示：L = [("A","B"), ("B","C"), ("C","D"), ("E","F"), ("G","H"), ("H","I"), ("G","I"), ("G","J")]使用 python 我想有效地将此列表拆分为：L1 = [("A","B"), ("B","C"), ("C","D")]L2 = [("E","F")]L3 = [("G","H"), ("G","I"), ("G","J"), ("H","I")]如何有效地将列表分成成对的组，其中对于组中的对，必须始终至少有一对与其他人共享一个项目？正如其中一个答案所述，这实际上是网络问题。目标是有效地将网络拆分为断开连接的（隔离的）网络部分。可以更改类型列表、元组（集）以实现更高的效率。

Answer 1

这更像是一个网络问题，所以我们可以使用networkx：

import networkx as nx

G=nx.from_edgelist(L)

l=list(nx.connected_components(G))

# after that we create the map dict , for get the unique id for each nodes

mapdict={z:x for x, y in enumerate(l) for z in y }

# then append the id back to original data for groupby 

newlist=[ x+(mapdict[x[0]],)for  x in L]

import itertools

#using groupby make the same id into one sublist

newlist=sorted(newlist,key=lambda x : x[2])

yourlist=[list(y) for x , y in itertools.groupby(newlist,key=lambda x : x[2])]

yourlist

[[('A', 'B', 0), ('B', 'C', 0), ('C', 'D', 0)], [('E', 'F', 1)], [('G', 'H', 2), ('H', 'I', 2), ('G', 'I', 2), ('G', 'J', 2)]]

然后匹配您的输出格式：

L1,L2,L3=[[y[:2]for y in x] for x in yourlist]

L1

[('A', 'B'), ('B', 'C'), ('C', 'D')]

L2

[('E', 'F')]

L3

[('G', 'H'), ('H', 'I'), ('G', 'I'), ('G', 'J')]

Answer 2

• 将组列表初始化为空

• 让我们(a, b)成为下一对

• 收集包含带有a或的任何元素的所有组b

• 将它们全部删除，加入它们，添加(a, b)，然后作为新组插入

• 重复直到完成

那会是这样的：

import itertools, functools

def partition(pred, iterable):

    t1, t2 = itertools.tee(iterable)

    return itertools.filterfalse(pred, t1), filter(pred, t2)

groups = []

for a, b in L:

    unrelated, related = partition(lambda group: any(aa == a or bb == b or aa == b or bb == a for aa, bb in group), groups)

    groups = [*unrelated, sum(related, [(a, b)])]

Answer 3

一种高效的 Pythonic 方法是将元组列表转换为一组frozensets 作为候选池，并在while循环中，创建一组作为组并使用嵌套while循环通过添加第一个候选集和然后与与该组相交的其他候选集执行集合并集，直到没有更多的相交候选集，此时返回外循环以形成一个新组：

pool = set(map(frozenset, L))

groups = []

while pool:

    group = set()

    groups.append([])

    while True:

        for candidate in pool:

            if not group or group & candidate:

                group |= candidate

                groups[-1].append(tuple(candidate))

                pool.remove(candidate)

                break

        else:

            break

鉴于您的样本输入，groups将变为：

[[('A', 'B'), ('C', 'B'), ('C', 'D')],

 [('G', 'H'), ('H', 'I'), ('G', 'J'), ('G', 'I')],

 [('E', 'F')]]

请记住，集合在 Python 中是无序的，这就是为什么上述输出的顺序与您的预期输出不匹配的原因，但对于您的目的而言，顺序应该无关紧要。