Encontrar combinaciones de N establece que no más de un elemento en común.

Question

Definición del problema;

Hay N conjuntos de entrada, de los tamaños de las $S_1, S_2, ... ,S_N$.
por ejemplo; 4 - (1a,2a,3a,4a,5a), (1b,2b,3b,4b), (1c,2c,3c), (1d,2d,3d)

Una combinación se realiza mediante la selección de un elemento de cada conjunto de entrada.
por ejemplo; [1a, 1b, 1c, 1d]

Regla: No hay combinación elegida puede tener más de un elemento en común con cualquier otro.
por ejemplo, si [1a, 1b, 1c, 1d] es una combinación, ninguna otra combinación puede tener más de uno de 1a, 1b, 1c, 1d.

El objetivo es hacer un conjunto de salida que contiene el número máximo de combinaciones permitidas por la regla.
por ejemplo ([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])

Hasta ahora he;

1. Se dieron cuenta de que sin la regla, simplemente hay $S_1 \times S_2 \times \dots \times S_N$ combinaciones, y que la respuesta es algún subconjunto de esas.
2. Escrito por fuerza bruta solver que encuentra diferentes combinaciones válidas.
3. Se dieron cuenta de que para muchos de los casos el mayor número de combinaciones válidas es el producto de la menor de dos tamaños.
   Pero no todos; Por ejemplo, si los conjuntos de entrada tienen tamaños de $\{3,3,3,3,3\}$ sólo hay $6$ combinaciones válidas.
4. Di cuenta de que no son los máximos locales que tengan cuidado de que no todos los parciales de salida puede ser completado con el mismo tamaño.
   por ejemplo, para los tamaños de $\{2,2,2\}$, si el parcial de salida es ([1a,1b,1c],[2a,2b,2c], ...) no se pueden añadir más.

Me gustaría;

1. Calcular cuántas combinaciones hay sin fuerza bruta de problemas, teniendo en cuenta algunas conjunto de entrada de los tamaños de $S_0, S_1, ... ,S_N$.
2. De un total $T$, calcular el mayor número de combinaciones que pueden ser producidos a partir de la entrada de los tamaños de los conjuntos de sumar a $T$; $T = \sum_{i=1}^N S_i$.

---

No-Solución

He encontrado un sub-problema, que si resueltos podría ser una solución a este problema.

Si uno toma la solución para $N-1$ de los conjuntos de entrada y los pone en un mínimo número de conjuntos de combinaciones únicas (cero elementos en común), a continuación, $S_N$ de los conjuntos puede ser completado con un elemento de la $N^{th}$.

Ejemplo:

1. Si los tamaños son $\{3, 3, 3\}$, ver el $\{3,3\}$
2. Las combinaciones son ([1a,1b],[1a,2b],[1a,3b],[2a,1b],[2a,2b],[2a,3b],[3a 1b],[3a,2b],[3a,3b])
3. Encontrar el mínimo número de conjuntos de combinaciones de cero elementos comunes:
   • ([1b,1c],[2b,2c],[3b,3c])
   • ([1b,2c],[2b,1c])
   • ([1b,3c],[3b,1c])
   • ([2b,3c],[3b,2c])
4. Completa en la mayoría de las $S_N$ de esas filas con los valores de $N^(th)$ conjunto de: (el más grande de los conjuntos de primera)
   • ([1a,1b,1c],[1a,2b,2c],[1a,3b,3c])
   • ([2a,1b,2c],[2a,2b,1c])
   • ([3a,1b,3c],[3a,3b,1c])

Esto se refiere a la razón por la que el número de combinaciones no es siempre el producto de los dos más pequeños tamaños de los conjuntos.
No estoy seguro de que a pesar de cómo resolver paso 3 - suena como un problema interesante en sí mismo.

Answer 1

Parece que el siguiente.

Indicar el número máximo de combinaciones con determinado conjunto de tamaños de $S_1\le S_2\le \cdots\le S_N$$C(S_1,\dots, S_N)$.

1. Suponga que el total $T=S_1+\cdots+S_N$ es dado. Desde $C(S_1,\dots, S_N)\le S_1S_2$ y esta máxima se alcanza cuando $N=2$, $C(S_1,\dots, S_N)\le S_1(T-S_1)$ y es fácil ver que la igualdad se alcanza cuando $S_1=\lfloor T/2\rfloor$. Que es $S_1=T/2$ si $T$ es incluso y $S_1=T-1/2$ si $T$ es impar. En ambos casos, el máximo es de $\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

o

1a1b1c 1a2b2c 1a3b3c

2a1b3c 2a2b1c 2a3b2c

3a1b2c 3a2b3c 3a3b1c

4. A partir del 2., es fácil comprobar que C(2,2,2,2)=2.

5. Matriz ortogonal representación de un cuadrado latino muestra que $C(n,n,n)=n^2$

6. Por otra parte, desde Greco-latina existen plazas para todos los pedidos de $n\ge 3$ con la excepción de $n = 6$, tenemos $C(n,n,n,n)=n^2$ estos $n$.

7. Moremoreover, si iff (?) $N-2$ no es más grande que el número de condiciones mutuamente ortogonales de los cuadrados latinos y $S_1=S_2=\cdots=S_N=n$$C(S_1,\dots, S_N)=n^2$.