Setting Up A Recursive Function to Calculate Inclusion Exclusion in Python

Question

For those of you unfamiliar, the inclusion-exclusion principle sets out a way to determine the values of the union of intersecting sets without double counting. In short, if you have two sets A,B and they intersect it is possible to calculate the value of their union by adding the values of the two sets together and then subtracting their intersection to avoid double counting.

In other words,

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

This can be extended for any finite number of sets and even for an infinite number of sets. How might one construct a recursive function in Python that makes use of this principle?

Answer 1

Generally, you wouldn't use PIE. If you want the size of the union, take the union:

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

PIE is more useful in combinatorics, where you might have a set of 2 gazillion elements, a set of 3 gazillion elements, and a way to tell that their intersection contains 1 gazillion elements without going through all the elements one by one. In programming, though, you're not working with compact expressions that encode the sets. You have 5 gazillion elements sitting in memory. Intersecting the sets would require going through every one of 2 gazillion elements and seeing whether it's in the other set. There's no advantage to PIE.

If you want to use it anyway, the simplest way would be to use 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))