在 Python 中设置递归函数来计算包含排除

Question

对于不熟悉的人，包含-排除原则提供了一种无需重复计算即可确定相交集的并集值的方法。简而言之，如果您有两个集合 A、B 并且它们相交，则可以通过将两个集合的值相加然后减去它们的交集来计算它们并集的值以避免重复计算。

换句话说，

 $/mu(A /union B) = /mu(A) + /mu(B) - /mu(A /intersection B)$.  

这可以扩展到任何有限数量的集合，甚至无限数量的集合。如何在 Python 中构造一个利用这一原则的递归函数？

Answer 1

一般来说，您不会使用 PIE。如果您想要联合的大小，请获取联合：

def union_size(sets):
    return len(set.union(*sets))

PIE 在组合学中更有用，在组合学中，您可能有一组包含 2 个无数元素的集合、一组包含 3 个无数元素的集合，以及一种方法来判断它们的交集包含 1 个无数元素，而无需逐一遍历所有元素。但是，在编程中，您不会使用对集合进行编码的紧凑表达式。你的内存中有 5 个无数的元素。相交集合需要遍历 2 个无数元素中的每一个，并查看它是否在另一个集合中。PIE没有任何优势。

如果你想使用它，最简单的方法是使用itertools：

import itertools
def union_size(sets):
    return sum((-1)**(i+1) * len(set.intersection(*subset))
               for i in xrange(1, len(sets) + 1)
               for subset in itertools.combinations(sets, i))