## “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 *A*, *B* and *C*, the partitions are

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-(B∪C) |

0 | 1 | 0 | B-(A∪C) |

1 | 1 | 0 | (A∩B)-C |

0 | 0 | 1 | C-(A∪B) |

1 | 0 | 1 | (A∩C)-B |

0 | 1 | 1 | (B∩C)-A |

1 | 1 | 1 | A∩B∩C |

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 *A*∪*B*∪*C* 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 | ∅ | (((A∪B∪C) – C) – B) – A |

1 | 0 | 0 | A-(B∪C) |
(((A∪B∪C) – C) – B) ∩ A |

0 | 1 | 0 | B-(A∪C) |
(((A∪B∪C) – C) ∩ B) – A |

1 | 1 | 0 | (A∩B)-C |
(((A∪B∪C) – C) ∩ B) ∩ A |

0 | 0 | 1 | C-(A∪B) |
(((A∪B∪C) ∩ C) – B) – A |

1 | 0 | 1 | (A∩C)-B |
(((A∪B∪C) ∩ C) – B) ∩ A |

0 | 1 | 1 | (B∩C)-A |
(((A∪B∪C) ∩ C) ∩ B) – A |

1 | 1 | 1 | A∩B∩C |
(((A∪B∪C) ∩ 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:

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