Venn Diagram Cells

Question

Given multiple sets, e.g. s1={2,3,7}, s2={1,2,4,7,8} and s3={4,7}, a Venn diagram visualizes each set by a closed curve and set elements which are either inside or outside the curve's perimeter, depending on whether they are element of the set or not. Because all set elements appear only once in the Venn digram, the curves representing each set need to overlap if an element is present in more than one set. We call each such overlapping a cell of the Venn diagram.

This explanation might be a bit confusing, so let's have a look at an example.

Example

A Venn diagram for sets s1, s2 and s3 could look like this:

The cells of this Venn diagram are (read from top to bottom, left to right) {1,8}, {2}, {7}, {4}, {3}, {} and {}.

In practice, one commonly encounters only Venn diagrams of two or three sets, because the representation of Venn diagrams of four or more sets is not very clear. However they do exist, e.g. for six sets:

^{CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1472309}

The Task

Given a non-empty set of sets of positive integers in any reasonable representation, return the set of cells of the input sets' Venn diagram. Specifically, no graphical representation is needed.

• You may write a full program or a function.
• You may return as many empty sets as there are empty cells (i.e. a list of all cells) instead of just one empty set (i.e. the set of cells).
• Some reasonable ways of input for the above example include but are not limited to {{2,3,7},{1,2,4,7,8},{4,7}}, [[2,3,7],[1,2,4,7,8],[4,7]], "2,3,7;1,2,4,7,8;4,7" or "2 3 7\n1 2 4 7 8\n4 7". If in doubt whether your chosen input format is acceptable, feel free to ask in a comment.
• Your output format should match your input format, if possible. Note that this rule requires your format to be able to unambiguously display empty sets.
• This is code-golf, so try to use as few bytes as possible in the language of your choice. In order to encourage competition per language instead of between languages, I won't accept an answer.

Test Cases

Here are some inputs along with possible outputs:

input -> output
{{2,3,7},{1,2,4,7,8},{4,7}} -> {{1,8},{2},{7},{4},{3},{}} (or {{1,8},{2},{7},{4},{3},{},{}})
{{1,2,3},{4,5,6},{7,8,9}} -> {{1,2,3},{4,5,6},{7,8,9},{}}
{{}} -> {{}}
{{1,2,3},{1,2}} -> {{1,2},{3},{}}
{{4,3,8},{1,2,9,3},{14,7,8,5},{6,11,3,8},{10},{9,4,3,7,10}} -> {{6,11},{10},{4},{3},{8},{5,14},{1,2},{9},{7},{}}
{{2,3,4,7},{},{1,3,7,5,6},{2,3,7,5},{7,2,4,3,6},{1,4,5}} -> {{},{4},{2},{7,3},{1},{6},{5}}
{{1,2,3,4},{1,2,5,6},{1,3,5,7}} -> {{4},{3},{2},{1},{6},{5},{7}}

Answer 1

Haskell, 71 bytes

An anonymous function taking a list of lists of integers and returning a similar list.

Use as (foldr(\x r->(x\\(id=<<r)):([intersect x,(\\x)]<*>r))[])[[1,2,3],[1,2]].

import Data.List
foldr(\x r->(x\\(id=<<r)):([intersect x,(\\x)]<*>r))[]

Try it online!

How it works

• Uses the set-like operations \\ (difference) and intersect from Data.List.
• Folds the list of "sets" (represented as lists) into a list of cells, starting with the empty list [].
• x is the current set to be added to the diagram, and r is the list of cells already constructed.
  • x\\(id=<<r) is the subset of elements of x that are not in any of the already constructed cells.
  • [intersect x,(\\x)]<*>r splits up each cell in r according to whether its elements are in x or not.
• Most definitely does not attempt to merge empty cells, so there are quite a bit of those in the output.

Answer 2

Perl 5, 79 bytes

sub{for$.(0..@_){$x{$_}+=2**$.for@{$_[$.]}};push@{$h{$x{$_}}},$_ for keys%x;%h}

Takes input as a list of anonymous arrays like ([2,3,7],[1,2,4,7,8],[4,7]). Outputs a hash where the keys are labels and the values are anonymous arrays corresponding to the output sets.

As part of a full program:

*x=
sub{for$.(0..@_){$x{$_}+=2**$.for@{$_[$.]}};push@{$h{$x{$_}}},$_ for keys%x;%h};
%x=x([2,3,7],[1,2,4,7,8],[4,7]);
print"Set $_:@{$x{$_}}\n"for keys%x;

Explanation:

Gives each set an integer as a label, $.. Creates a hash that stores an integer for each unique element $_. Adds 2**$. for each set that $_ appears in, effectively making a binary map showing what sets each element appears in. Finally, makes an anonymous array for each cell of the Venn diagram and pushes the elements appearing in the corresponding sets to the array. So each element of each array exists in the same sets and thus the same cell of the Venn diagram.

Answer 3

Jelly, 14 17 bytes

FṀ‘³iþ¬Ḅµ;ṀḶ$ĠṖṖ€

Try it online!

Function submission (because the format Jelly prints lists in by default doesn't round-trip – it can't read its own output format – but a function inputs and outputs in the same format). The TIO link contains a footer that runs the function and prints its output in the same format that input is parsed.

Explanation

FṀ‘³iþ¬Ḅµ;ṀḶ$ĠṖṖ€
FṀ‘               Find the largest number that appears in any of the input sets, + 1
   ³ þ            For each number from 1 to that number, and each of the input sets
    i ¬             find whether the number is missing from the set
       Ḅ          Convert the list of missing sets into a single number using binary
         ;        Append
        µ ṀḶ$     all numbers from 0 to the maximum value minus 1
             Ġ    Group indexes by values
              ṖṖ€ Delete the last group and last element of other groups

The requirement that we output at least one empty set if not all the Venn diagram sections are used manages to take up over half the program here (it's responsible for the ’ that makes sure we have at least one group for non-matching elements, allowing us to keep track of how many sets there were originally, plus the last nine bytes of the source code except for the Ġ). The basic way in which we implement it is to ensure that all the 2^n Venn diagram subsets have at least one entry, by adding a dummy entry that will fill the "in no sets" section and (later) a dummy entry to each other section, then Ġ will output a group for each subset, which we can remove using ṖṖ€.

Answer 4

Pyth, 11 bytes

m-@Fds-Qdty

Test suite.

How it works

Each region of the Venn diagram represents elements that are in [certain combinations of the sets] but not in [the other sets].

So, we generate all the possible combinations (and remove the empty combinations) by finding the power set of the input.

For each combination generated, we find the intersection of the sets in the combination, and filter out the elements which are in the other sets.

m-@Fds-Qdty  input as Q
          y  power set
         t   remove the first one (empty combination)
m            for each combination d:
  @Fd            find the intersection of all the sets in d
 -               filter out those who are in
     s               the union of
      -Qd            the sets not in the combination
                     (input minus combination)

Answer 5

JavaScript (ES6), 123 bytes

a=>a.map((b,i)=>b.map(e=>m[e]|=1<<i),m=[])&&[...Array(1<<a.length)].map((_,i)=>m.map((e,j)=>e==i&&j).filter(j=>j)).slice(1)