我希望能够在Python中计算一组有限整数集合(这里实现为列表嵌套列表)的所有(不同的)交集(为避免混淆,问题末尾提供了正式定义):
> A = [[0,1,2,3],[0,1,4],[1,2,4],[2,3,4],[0,3,4]]
> all_intersections(A) # desired output
[[], [0], [1], [2], [3], [4], [0, 1], [0, 3], [0, 4], [1, 2], [1, 4], [2, 3], [2, 4], [3, 4], [0, 1, 4], [0, 3, 4], [1, 2, 4], [2, 3, 4], [0, 1, 2, 3]]
我有一个迭代执行的算法,但它相当缓慢(我应该发表吗?),一个测试案例如下:
[[0, 1, 2, 3, 4, 9], [0, 1, 4, 5, 6, 10], [0, 2, 4, 5, 7, 11], [1, 3, 4, 6, 8, 12], [2, 3, 4, 7, 8, 13], [4, 5, 6, 7, 8, 14], [0, 1, 9, 10, 15, 16], [0, 2, 9, 11, 15, 17], [1, 3, 9, 12, 16, 18], [2, 3, 9, 13, 17, 18], [9, 15, 16, 17, 18, 19], [0, 5, 10, 11, 15, 20], [1, 6, 10, 12, 16, 21], [10, 15, 16, 19, 20, 21], [5, 6, 10, 14, 20, 21], [11, 15, 17, 19, 20, 22], [5, 7, 11, 14, 20, 22], [2, 7, 11, 13, 17, 22], [7, 8, 13, 14, 22, 23], [3, 8, 12, 13, 18, 23], [13, 17, 18, 19, 22, 23], [14, 19, 20, 21, 22, 23], [6, 8, 12, 14, 21, 23], [12, 16, 18, 19, 21, 23]]
这个计算需要我大约2.5秒的时间。
有什么快速的方法吗?
正式定义(没有LaTeX模式实际上很难):令A = {A1,...,An}是一个由非负整数的有限集合Ai组成的有限集合。输出应该是集合{B的交集:B是A的子集}。
因此,正式算法是取A的所有子集的所有交集的并集。但这显然需要很长时间。
非常感谢!
[0]
。有三个子列表都包含有0(包含0的交集最低要求是一对列表共享0),这三个列表之间的所有三种组合都包含至少一个重叠值(第一和第二项也共享1
,第一和最后一项共享3
,第二和最后一项共享4
)。难道你是将它们全部相交在一起? - ShadowRangerA
中执行所有集合的交集。对于仅涉及两个集合的交集,我会使用术语“逐对交集”,但我会执行所有交集。对于造成的混淆,我很抱歉! - Christian