如何基于共同项有效地分组成对？

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")]

如何高效地将列表分成成对的组，其中对于组中的成对，必须始终至少有一对与其他成对共享一个项目？ 如在其中一个答案中所述，实际上这是网络问题。目标是将网络有效地分割为不连通（孤立）的网络部分。

类型列表、元组（集合）可以更改以实现更高的效率。

- Miro

---

我很好奇这个的真实世界例子是什么。使用一对字母，您只会得到26*26种可能的选择。一旦您处理了重复项，输入大小将为O(1)，因此较慢的算法也足够。 - Leonid

@Leonid，归根结底这是一个网络问题 - 试图找到孤立的网络。每个元组都代表着起点和终点的线路。 - Miro

Miro，感谢您发布这个问题 - 我有同样的问题 - 应用程序 @Leonid：我想要确定成对值的集合(set())，其中每个成对值都是各个元素之间的相关性，例如：(1,2),(1,3),(2,3),(5,7)(5,4) -> (1,2,3), (4,5,7)。 这些也可以是所有天线（1,2,3），涉及到基线（1,2），（1,3），（2,3）等连接相关天线的射电望远镜阵列中的天线。 推论来自baseline数据，但我们希望通过编程方式知道涉及哪些天线。 - jtlz2

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')]

- BENY

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)])]

- Amadan

Answer 3

一种高效且符合Python风格的方法是将元组列表转换为候选项的冻结集合池，然后在一个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 中的集合是无序的，这就是为什么上面输出的顺序与您的预期输出不匹配，但是对于您的目的来说，顺序并不重要。

- blhsing

Answer 4

您可以使用以下代码：

l = [("A","B"), ("B","C"), ("C","D"), ("E","F"), ("G","H"), ("H","I"), ("G","I"), ("G","J")]

result = []
if len(l) > 1:
  tmp = [l[0]]
  for i in range(1,len(l)):
    if l[i][0] == l[i-1][1] or l[i][1] == l[i-1][0] or l[i][1] == l[i-1][1] or l[i][0] == l[i-1][0]:
      tmp.append(l[i])
    else:
      result.append(tmp)
      tmp = [l[i]]
  result.append(tmp)
else:
  result = l

for elem in result:
  print(elem)

output:

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

注意：此代码基于您的初始数组已排序的假设。如果不是这种情况，它将无法正常工作，因为它只对整个列表进行一次遍历以创建组（复杂度O(n)）。

解释：

• result将存储您的分组
• if len(l) > 1:如果您的列表中只有一个元素或为空列表，则无需进行任何处理，您已经得到了答案
• 您将在列表的每个元素上进行一次遍历，并比较元组在位置i和位置i-1之间的4种可能的等式。
• tmp用于构建您的组，只要满足条件，就向tmp添加元组
• 当条件未被满足时，您将添加tmp（已创建的当前组）到结果中，重新初始化tmp为当前元组并继续。

- Allan

---

即使是有序列表，这也并不总是有效：l = [("A","E"), ("B","C"), ("C","E")] - fireattack

Answer 5

你可以使用 while 循环并从 L 的第一个成员开始迭代（使用 for 循环内部）。检查整个列表是否有任何成员（两者之一）被共享。然后将其附加到列表 L1 中，并从原始列表 L 中弹出该成员。然后 while 循环会再次运行（直到列表 L 不为空）。对于每个要附加到新列表 L2 中的元素，循环内部都会运行。你可以尝试这个方法。（我提供代码，这不会有帮助）

- Tojra