# Find combinations of N sets having no more than one item in common.

## Problem definition;

There are N input sets, of sizes $S_1, S_2, ... ,S_N$.
eg; 4 sets - (1a,2a,3a,4a,5a), (1b,2b,3b,4b), (1c,2c,3c), (1d,2d,3d)

A combination is made by selecting one item from each input set.
eg; [1a, 1b, 1c, 1d]

Rule: No chosen combination may have more than one item in common with any other.
eg if [1a, 1b, 1c, 1d] is one combination, no other combination may have more than one of 1a, 1b, 1c, 1d.

The aim is to make an output set containing the maximum number of combinations allowed by the rule.
eg ([1a,1b,1c,1d],[1a,2b,2c,2d],[1a,3b,3c,3d],[2a,1b,2c,3d],[2a,2b,3c,1d],[2a,3b,1c,2d],[3a,1b,3c,2d],[3a,2b,1c,3d],[3a,3b,2c,1d])

## So far I've;

1. Realised that without the rule, there are simply $S_1 \times S_2 \times \dots \times S_N$ combinations, and that the answer is some subset of those.
2. Written a brute-force solver that finds different valid combinations.
3. Realised that for many cases the highest number of valid combinations is the product of the smallest two set sizes.
But not all; For example if input sets have sizes $\{3,3,3,3,3\}$ there's only $6$ valid combinations.
4. Realised that there are local maxima to beware of - not all partial output sets can be completed to the same size.
eg for sizes $\{2,2,2\}$, if the partial output set is ([1a,1b,1c],[2a,2b,2c], ...) no more can be added.

## I'd like to;

1. Calculate how many combinations there are without brute-force solving, given some input set sizes $S_0, S_1, ... ,S_N$.
2. From a given total $T$, calculate the highest number of combinations that can be produced from input set sizes summing to $T$; $T = \sum_{i=1}^N S_i$.

## Not-Solution

I've found a sub-problem that if solved might be a solution to this problem.

If one takes the solution for $N-1$ of those input sets and puts them into a minimal number of sets of completely unique combinations (zero items in common), then $S_N$ of those sets can be completed with an element from the $N^{th}$ set.

Example:

1. If sizes are $\{3, 3, 3\}$, look at $\{3,3\}$
2. Combinations are ([1a,1b],[1a,2b],[1a,3b],[2a,1b],[2a,2b],[2a,3b],[3a,1b],[3a,2b],[3a,3b])
3. Find minimal number of sets of combinations of zero common items:
• ([1b,1c],[2b,2c],[3b,3c])
• ([1b,2c],[2b,1c])
• ([1b,3c],[3b,1c])
• ([2b,3c],[3b,2c])
4. Complete at most $S_N$ of those rows with values from the $N^(th)$ set: (largest sets first)
• ([1a,1b,1c],[1a,2b,2c],[1a,3b,3c])
• ([2a,1b,2c],[2a,2b,1c])
• ([3a,1b,3c],[3a,3b,1c])

This addresses the reason that the number of combinations is not always the product of the two smallest set sizes.
I'm not sure though how to solve step 3 - it sounds like an interesting problem in itself.

• For point 3 of "So far", have you proven that it is less than or equal that number? Commented Dec 27, 2015 at 1:23
• As @Element118 suggests, there is a simple proof to show that the product of the two smallest set sizes is an upper bound (hint: pigeon-hole principle). You should even be able to show easily that if the third smallest size is larger than the product of the two smallest, then this upper bound can be achieved.
– Snow
Commented Dec 27, 2015 at 1:53
• For part 2 of "I'd like to", is $N$ fixed or can it be varied? Commented Dec 27, 2015 at 5:22
• @Element118 as Snow says the upper bound is the product of the two smallest set sizes. I don't have a complete solution for when it's not achievable. Commented Dec 27, 2015 at 11:34
• For part 2 of "I'd like to", $N$ is "number of sets" and set sizes form "partitions" of $T$. $N$ is an input that will be adjusted to find a case where the number of combinations is more than a threshold. Commented Dec 27, 2015 at 11:44

It seems the following.

Denote the maximal number of combinations with given set sizes $$S_1\le S_2\le \cdots\le S_N$$ as $$C(S_1,\dots, S_N)$$.

1. Assume that the total $$T=S_1+\cdots+S_N$$ is given. Since $$C(S_1,\dots, S_N)\le S_1S_2$$ and this maximum is attained when $$N=2$$, we have that $$C(S_1,\dots, S_N)\le S_1(T-S_1)$$ and it is easy to see that the equality is attained when $$S_1=\lfloor T/2\rfloor$$. That is $$S_1=T/2$$ if $$T$$ is even and $$S_1=T-1/2$$ if $$T$$ is odd. In both cases the maximum is $$\lfloor T^2/4\rfloor$$.

2. C(2,2,2)=4:

1a1b1c 1a2b2c
2a1b2c 2a2b1c

1. C(3,3,3)=9:

1a1b1c 1a2b2c 1a3b3c

2a1b2c 2a2b3c 2a3b1c

3a1b3c 3a2b1c 3a3b2c

or

1a1b1c 1a2b2c 1a3b3c

2a1b3c 2a2b1c 2a3b2c

3a1b2c 3a2b3c 3a3b1c

1. Starting from 2., it is easy to check that C(2,2,2,2)=2.

2. Orthogonal array representation of a Latin square shows that $$C(n,n,n)=n^2$$

3. Moreover, since Graeco-Latin squares exist for all orders $$n\ge 3$$ except $$n = 6$$, we have $$C(n,n,n,n)=n^2$$ for these $$n$$.

4. Moremoreover, if (iff?) $$N-2$$ is not bigger than the number of mutually orthogonal latin squares and $$S_1=S_2=\cdots=S_N=n$$ then $$C(S_1,\dots, S_N)=n^2$$.