在Python中成对设置交集

Question

如果我有一个变量多套(我们称之为数Ñ),其中最多有米元件分别,什么是计算成对交叉将所有对套最有效的方法是什么？请注意,这与所有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"}}

我知道,这样做的一个方法是创建一个字典映射中的所有工会的每个值ñ套在它出现的集列表,然后通过所有这些值来创建列表如重复intersections_C以上,但我不确定n的增加是如何增加的,并且该组的大小变得太大.

一些额外的背景信息:

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