Conjunto contenedor optimo de combinaciones de inferior número de elementos
Dado un número de elementos N, y sean:
- A = {Combinaciones de N elementos tomadas de I en I }
- B = {Combinaciones de N elementos tomadas de J en J }
- I > J I,J Números naturales.
Calcular el subconjunto de A que con un mínimo de elementos, contenga todas las combinaciones de B.
Ejemplo
Sea E {1,2,3,4,5}; I=3; J=2
Entonces A será { {1,2,3},
{1,2,4},
{1,2,5},
{1,3,5},
{1,4,5},
{2,3,4},
{2,3,5},
{2,4,5},
{3,4,5} } Combinaciones de 5 elementos tomadas de 3 en 3
B será { {1,2},
{1,3},
{1,4},
{1,5},
{2,3},
{2,4},
{2,5},
{3,4},
{3,5},
{4,5} } Combinaciones de 5 elementos tomadas de 2 en 2
Y un subconjunto de A que contiene todos los elementos de B seria:
C { 1,2,3,
2,4,5,
1,4,5,
3,4,5 }
O sea,
{1,2,3} contiene {1,2} {1,3} {2,3}
{2,4,5} contiene {2,4} {2,5} {4,5}
{1,4,5} contiene {1,4} {1,5}
{3,4,5} contiene {3,4} {3,5}
Caso particular de especial interés
N=49, A=6 y B=3
E={1,2,3,4,5,6,7,…….,46,47,48,49}
A=Combinaciones de 49 elementos tomadas de 6 en 6, o sea 13.983.816 combinaciones.
B=Combinaciones de 49 elementos tomadas de 3 en 3, o sea 18.424 combinaciones.
Sabemos que de cada combinación de 6 elementos, se pueden crear 20 combinaciones de 3 elementos
O sea: Combinaciones de 6 elementos tomadas de 3 en 3, son 20 combinaciones.
Por tanto, teóricamente necesitaríamos 18.424/20 para poder representar todas las combinaciones de B con combinaciones de A
O sea: necesitamos 921,2 combinaciones de A, esto como mínimo, y en el caso ideal.
Surgen una serie de preguntas:
- ¿Cómo calculamos esas combinaciones?
- ¿Es posible cumplir el caso teórico, de 921,2 combinaciones, o seguramente serán necesarias más combinaciones?
El método de fuerza bruta para calcularlo seria así:
Evaluar todas las posibles combinaciones de 922 elementos del conjunto A, para seleccionar
La que más elementos de B represente.
Este método esta descartado, ya que el número de dichas combinaciones seria:
Combinaciones de 13.983.816 elementos tomadas de 922 en 922, lo cual es un número inmenso, de un orden de magnitud de millones de ceros. Seguramente que el ordenador más potente seria incapaz de procesar todo ese trabajo, ni en toda la existencia del universo.
Y ojo! Que después de tanto esfuerzo, obtendríamos el mejor grupo de los de 922 elementos. Pero puede ser que el mejor grupo de todos sea de un número mayor de elementos (a determinar).
Por tanto es necesaria una observación o idea genial, para poder resolver este problema, en nuestra existencia finita………… Que seguramente podremos conseguirla entre todos en este foro.
