python - 在Python中成对设置交集

如果我有一个可变的集合数（我们称之为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的增加和s的大小而扩展。ET过大。
一些其他背景信息：
每个集合的长度大致相同，但也非常大（足够大，可以将它们全部存储在内存中是一个现实问题，并且可以避免这种情况的算法是首选的，但不是必需的）
与集合本身的大小相比，任何两个集合之间的交集的大小都非常小。
如果它有帮助的话，我们可以假设关于输入集顺序的任何需要。

最佳答案

这个应该做你想做的

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都是迭代器。

关于python - 在Python中成对设置交集，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27369373/