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

Question

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.

Answer 1

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

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

1a1b1c 1a2b2c 1a3b3c

2a1b2c 2a2b3c 2a3b1c

3a1b3c 3a2b1c 3a3b2c

or

1a1b1c 1a2b2c 1a3b3c

2a1b3c 2a2b1c 2a3b2c

3a1b2c 3a2b3c 3a3b1c

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

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

6. 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$.

7. 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$.