The problem

At the beginning of the nVenn procedure, we want to build a Venn diagram with n sets. This means that we need to find closed curves that intersect to give all the possible regions of the diagram. With the help of boolean chain decomposition, we can accomplish this with simple curves by starting with a particular ordering of the regions themselves.

Some definitions

• We will represent each region with a binary chain
• Each position in the chain refers to a set, beginning from the left
• For each position in the chain, 1 means "belongs to" and 0 means "does not belong to "
• For matching purposes, we can generate the m-chain by changing each 0 in the chain with a (, and each 1 with a )
• Following the rules of parenthesis-matching, we say that a 0 or a 1 is unmatched if its corresponding parenthesis in the m-chain is unmatched

One example: the chain 0010011 gives information about 7 sets. Reading from left to right, this means that the region belogs to sets 3, 6 and 7 (positions of the 1s) and does not belong to any other region. The corresponding m-chain would be ( ( ) ( ( ) ) . Therefore, the first zero from the left is unmatched, and the rest of the positions are matched (as shown in colors).

The algorithm

First, the description of the algorithm. It may be confusing, but afterwards we will see it in action.

• Start with the chain filled with zeroes
• GetBranches: Recursively change to 1 the first 0 to the right of the last 1 (or the first position) if the resulting chain has no unmatched 1s. Each new chain is placed to the right of the preceding chain.
• FillBranches: For each of the chains generated in the previous step, consecutively change the first unmatched 0 to 1 until no unmatched 0s remain. Each chain is placed above the preceding chain.

The FillColumn procedure ensures that, if a region has a 1 at any position, every region above also has a one at that position. For this reason, the final curves for the sets are easy to generate.

Example

Click repeatedly on the figure below to see each step in action for 3 sets 4 sets 5 sets . At each step, the blue V locates the active chain in the algorithm. The bit under consideration is in red.

This algorithm works for any number of groups. If you want to see what a larger Venn diagram looks like, you can click here for 6 sets 7 sets 8 sets 9 sets 10 sets . The animation will be automatic. Warning: the animation with more than 7 sets may be too complex for some devices.

Proportionality

In the nVenn algorithm, the program places circles inside each region. The area of those circles is proportional to the number of elements in its region. Then, the lines shrink to adapt to those circles as shown in the video (the viewport zooms as the figure shrinks):