python - Python 中的成对集交集

Question

如果我有可变数量的集合(我们称其为 n)，每个集合最多有 m 个元素，计算成对的最有效方法是什么所有对集合的交点？请注意，这与所有 n 集的交集不同。

例如，如果我有以下集合:

A={"a","b","c"}
B={"c","d","e"}
C={"a","c","e"}

我希望能够找到:

intersect_AB={"c"}
intersect_BC={"c", "e"}
intersect_AC={"a", "c"}

另一种可接受的格式(如果它使事情更容易)是给定集合中的项目到包含相同项目的集合的映射。例如:

intersections_C={"a": {"A", "C"},
                 "c": {"A", "B", "C"}
                 "e": {"B", "C"}}

我知道这样做的一种方法是创建一个字典，将所有 n 集合并集中的每个值映射到它出现的集合列表，然后遍历所有这些值用于创建列表，例如上面的 intersections_C，但我不确定随着 n 的增加和集合的大小变得太大，它是如何扩展的。

一些额外的背景信息:

1. 每个集合的长度大致相同，但也非常大(大到足以将它们全部存储在内存中是一个现实的问题，虽然没有必要，但最好使用一种算法来避免这种情况)
2. 与集合本身的大小相比，任意两个集合之间的交集的大小都非常小
3. 如果有帮助，我们可以假设我们需要的关于输入集排序的任何内容。

Answer 1

这应该做你想做的

import random as RND
import string
import itertools as IT

模拟一些数据

fnx = lambda: set(RND.sample(string.ascii_uppercase, 7))
S = [fnx() for c in range(5)]

生成 S 中集合的索引列表，以便可以在下面更简洁地引用这些集合

idx = range(len(S))

获取 S 中所有可能的唯一项目对；然而，由于集合交集是可交换的，我们需要组合而不是排列

pairs = IT.combinations(idx, 2)

写一个函数执行集合交集

nt = lambda a, b: S[a].intersection(S[b])

将这个函数折叠在对上，并将每个函数调用的结果键值对它的参数

res = dict([ (t, nt(*t)) for t in pairs ])

下面的结果，按照 OP 中引用的第一个选项格式化，是一个字典，其中值是两个序列的集合交集；每个值键控到一个由这些序列的两个索引组成的元组

这个解决方案实际上只是两行代码:(i) 计算排列； (ii) 然后对每个排列应用一些函数，将返回值存储在结构化容器(键值)容器中

这个解决方案的内存占用是最小的，但你可以通过在最后一步返回一个生成器表达式来做得更好，即

res = ( (t, nt(*t)) for t in pairs )

请注意，使用这种方法时，对的序列和相应的交集都没有在内存中写出——即，对 和res 都是迭代器。