“Venn diagram” partitioning

2013-07-10 § Leave a comment

Paddy3118 wrote about partitioning elements in the same way a Venn diagram does. So, if we have sets AB and C, the partitions are

Image

These partitions can be organised in a table according to whether each of A, B and C is included or excluded:

A   B   C     partition
1 0 0  A-(BC)
0 1 0  B-(AC)
1 1 0  (AB)-C
0 0 1  C-(AB)
1 0 1  (AC)-B
0 1 1  (BC)-A
1 1 1  ABC

and the question is how to write a function that will return this sequence of partitions. Paddy3118 writes it like this:

def venndiv(*sets):
    bins = tuple(set() for n in range(2**len(sets)))
    for i, si in enumerate(sets): # Over every individual item of each set
        for item in si:
            binindex = 0
            for j, sj in enumerate(sets): # Test for membership of each set
                if item in sj:
                    binindex += 2**j # Binary count binning
            bins[binindex].add(item)
    return bins[1:] # bins[0] - an item in no set is impossible.

which is perfectly good: the explicit manipulation of index numbers is a little inelegant, perhaps. This post describes a different, pleasingly simple, way to express the venndiv function.

The first thing to notice is that there is a systematic way to build up the partitions by starting with ABC and taking intersections and differences with A, B and C. Where there is a 1 in the table, take an intersection with that set, and where there is a 0 subtract that set. You can do these steps in any order. Here is the table again, with systematic expressions included:

A   B   C     partition   systematic
0 0 0  ∅  (((ABC) – C) – B) – A
1 0 0  A-(BC)  (((ABC) – C) – B) ∩ A
0 1 0  B-(AC)  (((ABC) – C) ∩ B) – A
1 1 0  (AB)-C  (((ABC) – C) ∩ B) ∩ A
0 0 1  C-(AB)  (((ABC) ∩ C) – B) – A
1 0 1  (AC)-B  (((ABC) ∩ C) – B) ∩ A
0 1 1  (BC)-A  (((ABC) ∩ C) ∩ B) – A
1 1 1  ABC  (((ABC) ∩ C) ∩ B) ∩ A

So we can build the partitions starting with the C’s, then the B’s and then the A’s, like this:
venn-tree

The bottom row has all the partitions, in the right order. So our algorithm is: make a recursive call to fetch the second-to-last row, then split each bin into (bin - A) and (bin ∩ A). In Python:

def venndiv(*sets):
    def vd(x, *xs):
        bins = vd(*xs) if xs else (set.union(*sets),)
        return sum(tuple( (bin - x, bin & x) for bin in bins ), ())
    return vd(*sets)[1:]

Or maybe it’s clearer as a loop, rather than a recursive function:

def venndiv(*sets):
    bins = ( set.union(*sets), )
    for x in reversed(sets):
        bins = sum(tuple( (bin - x, bin & x) for bin in bins ), ())
    return bins[1:]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

What’s this?

You are currently reading “Venn diagram” partitioning at Bosker Blog.

meta

Follow

Get every new post delivered to your Inbox.

Join 690 other followers

%d bloggers like this: