# Find all intersections of subsets.

I am having trouble with what seems like it should be a simple problem. I am trying to find intersections of connections between multiple people but I want to include any intersection of connections found between any two of the sets.

For example, Let

$A$ = {January, February, March, April, May, August}

$R$ = {January, February, March, April, September, October, November, December}

$Y$ = {January, February, May, July}

Now, $A \cap R \cap Y$ = {January, February},

but $A \cap R$ = {January, February, March, April},

$A \cap Y$ = {January, February, May},

and $R \cap Y$ = {January, February}

So what I really want is {January, February, March, April, May}

Now, I may not just have $A, R,$ and $Y$, I may have a lot more to sift through. Is there a more simple principle that I am missing to group all of these intersections together as a subset?

One thing I thought of was creating a graph, but I am rusty on my graph algorithms. Any suggestions though would be great.

Thanks!

-

It looks like you want any month that is in more than one subset. You can go through all the months and count how many subsets each one is in. If it is greater than one, put it in your final list.

-
Ok, cool. Thanks. Is there not a more underlying principle that doesn't require me to go through each set and count how many times an element appears? I'm speaking from a programming standpoint I guess. It seems like that is really my only option though, huh? – mharris7190 Jul 3 '14 at 17:04
Depending on how things are stored, it might be faster to make an array for the months, initialize to zero, then read each subset once and increment the elements of the array for each month that is in the subset. This will be much better if most months are not in most subsets. Say you had 5000 months and 3000 subsets. The first answer would need $5000*3000$ inquiries. The second would only need the total of the sizes of the $3000$ subsets. – Ross Millikan Jul 3 '14 at 17:08

The set you are after can be formalised thus:$\bigcup\limits_{\substack{A,B \in I \\ A \ne B}} A\cap B$, where $I$ is your set of subsets (i.e. in the example you gave $I=\{A,R,Y\}$).

This will give you the set of elements that are in at least two of your subsets.

In terms of a programming standpoint, I think you would have to go through each month in turn and count how many subsets it is in. Once you count it twice you can add it to your result set and move on to the next month.

-