如何快速在Python中获取所有集合的交集

Question

我希望能够在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的所有子集的所有交集的并集。但这显然需要很长时间。

非常感谢！

- Christian

---

这更像是“输入集合的并集的所有子集”。 - kennytm

两个列表的交集是什么意思？列表没有明确定义的交集运算符，但集合有。例如 - [0,1] 与 [1,0] 的交集是空的吗？[0,1]？[1,0]？另外 - 你是指所有列表对的交集还是所有列表元组的交集（包括三元组等）？ - John Coleman

为什么你需要这样做？ - Blender

我不确定你如何在第一个示例的期望输出中得到[0]。有三个子列表都包含有0（包含0的交集最低要求是一对列表共享0），这三个列表之间的所有三种组合都包含至少一个重叠值（第一和第二项也共享1，第一和最后一项共享3，第二和最后一项共享4）。难道你是将它们全部相交在一起？ - ShadowRanger

是的，我在大列表 A 中执行所有集合的交集。对于仅涉及两个集合的交集，我会使用术语“逐对交集”，但我会执行所有交集。对于造成的混淆，我很抱歉！ - Christian

Answer 1

这里是一个递归解决方案。在您的测试示例上几乎瞬间完成：

def allIntersections(frozenSets):
    if len(frozenSets) == 0:
        return []
    else:
        head = frozenSets[0]
        tail = frozenSets[1:]
        tailIntersections = allIntersections(tail)
        newIntersections = [head]
        newIntersections.extend(tailIntersections)
        newIntersections.extend(head & s for s in tailIntersections)
        return list(set(newIntersections))

def all_intersections(lists):
    sets = allIntersections([frozenset(s) for s in lists])
    return [list(s) for s in sets]

编辑说明 这里提供了一个更简洁、非递归实现相同想法的方法。

如果你定义一个空集合的交集为全集，那么可以通过取所有元素的并集来获得一个足够的全集。这是格论中的标准操作，它与将空集合的并集定义为空集合是对偶的。如果不需要，则可随时丢弃这个全集：

def allIntersections(frozenSets):
    universalSet = frozenset.union(*frozenSets)
    intersections = set([universalSet])
    for s in frozenSets:
        moreIntersections = set(s & t for t in intersections)
        intersections.update(moreIntersections)
    return intersections

def all_intersections(lists):
    sets = allIntersections([frozenset(s) for s in lists])
    return [list(s) for s in sets]

在你的测试样例中，这样快的原因是，即使你的集合有24个元素，有着2 ** 24（1680万）个潜在的交叉点，实际上只有242个（如果不计算空的交叉点，那么就只有241个）不同的交叉点。因此，每次循环中的交叉点数量最多只有几百个。

有可能选择24个集合，使得所有2 ** 24个可能的交叉点都是不同的，因此可以很容易地看出最坏情况下的行为是指数级的。但是，如果像在你的测试样例中一样，交叉点的数量很少，那么这种方法将允许您快速计算它们。

一个可能的优化是，在循环之前按大小递增对集合进行排序。处理较小的集合可能会导致更多的空交叉点出现在较早的位置，从而保持总交叉点数较小，直到循环结束为止。

- John Coleman

---

太好了！“这是格理论中的标准操作”：我确实需要那个集合，以便将其变成格子（否则，联接就没有定义）。 - Christian

我有一个后续问题，https://dev59.com/Lpffa4cB1Zd3GeqP_7hC，如果您有兴趣思考它的话。 - Christian

@ChristianStump，听起来很有趣，但我不确定今天是否有足够的时间认真考虑它。我有一些家庭事务要处理。 - John Coleman

Answer 2

迭代解决方案，在我的机器上针对您的大型测试输入需要约3.5毫秒：

from itertools import starmap, product
from operator import and_

def all_intersections(sets):
    # Convert to set of frozensets for uniquification/type correctness
    last = new = sets = set(map(frozenset, sets))
    # Keep going until further intersections add nothing to results
    while new:
        # Compute intersection of old values with newly found values
        new = set(starmap(and_, product(last, new)))
        last = sets.copy()  # Save off prior state
        new -= last         # Determine truly newly added values
        sets |= new         # Accumulate newly added values in complete set
    # No more intersections being generated, convert results to canonical
    # form, list of lists, where each sublist is displayed in order, and
    # the top level list is ordered first by size of sublist, then by contents
    return sorted(map(sorted, sets), key=lambda x: (len(x), x))

基本上，它只是在旧结果集和新发现的交集之间进行双向交集，直到一轮交集不再改变任何内容为止，然后就完成了。

注意：这实际上并不是最好的解决方案（递归在算法上足够好以赢得测试数据，在添加排序到外部包装器以匹配格式后，John Coleman的解决方案大约需要0.94毫秒，而我的需要3.5毫秒）。我主要提供它作为用其他方式解决问题的示例。

- ShadowRanger

---

@ChristianStump：实际上，这几乎不需要时间，因为集合要么在增长，要么不在增长，当它增长时，“!=”比较通过简单地检查长度并继续移动来短路（首先测试长度，仅当长度匹配时才进行逐个元素检查）。缺陷主要在于重复的工作；它正在重新组合已经在以前的循环中组合过的元素。 - ShadowRanger

@ChristianStump：我的解释现在有些错误，因为我改进了它以消除那个缺陷（它现在将新发现的交点与旧的相交，避免了在第二次和后续循环中再次相交旧的问题）。但它仍然有一些额外的开销，包括set构建、set复制和set差异，这是递归解决方案避免的，所以它仍然比较慢。 - ShadowRanger

这很好。我以前不熟悉starmap。我继续惊讶于使用itertools可以做多少事情。 - John Coleman

我有一个后续问题，https://dev59.com/Lpffa4cB1Zd3GeqP_7hC， 如果您有兴趣思考一下。 - Christian