设置一个递归函数来计算Python中的包含排除

对于那些你不熟悉的人来说，包含 - 排除原则规定了一种确定不重复计算相交集合的值的方法。简而言之，如果你有两组A和B并且它们相交，可以通过将两组数值相加在一起，然后减去它们的相交以避免重复计算来计算它们的联合值。设置一个递归函数来计算Python中的包含排除

换句话说，

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

这可以扩展为任意有限数目的组，甚至组的无限数量。如何在Python中构造一个使用这个原则的递归函数？

来源

2014-01-30 114

你能告诉我们你第一次尝试？ – Cilyan

@Cilyan嗯，说实话，我不知道从哪里开始。你有什么提示从哪里开始？ – 114

“利用这个原则” - 做什么？如果你想计算工会的规模，只要参加工会。 PIE对于我们在编程中倾向于使用的那些类型不那么有用。 – user2357112

一般来说，你不会使用PIE。如果你想在联盟的规模，采取联合：

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

PIE是在组合学，在那里你可以有一组2组极大数的元素，一组3个极大数的元素更加有用，并以某种方式告诉他们的交集包含1个gazillion元素，而不需要逐一浏览所有元素。但是，在编程中，您并不使用编码集合的紧凑表达式。你有5个gazillion元素坐在记忆中。相交集合需要通过2个gazillion元素的每一个元素并且看看它是否在另一个集合中。 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))

来源

2014-01-30 18:34:14 user2357112

关于编程方面的差异以及可能的方法正是我所期待的。我发现我需要多练习，以便能够立即看到这些事情。谢谢！ – 114

只用套。

AuB = set(A).union(B) 
len(AuB)

如果你想要AnB，你也可以使用set.intersection。

lenAuB = len(A) + len(B) - len(set(A).intersection(B))

（我假设A和B具有在上线没有重复项）

来源

2014-01-30 18:19:04 MatthieuBizien

这是一个很好的开始，谢谢！ – 114

+1为介绍这些想法，但用户的答案提供了一个更强大的解释，为什么我的想法如何PIE应该在这里工作是错误的。 – 114

设置一个递归函数来计算Python中的包含排除

回答

相关问题