設置一個遞歸函數來計算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中的包含排除

回答

相關問題