Autor Tema: Problema con Combinatorias

0 Usuarios y 1 Visitante están viendo este tema.

19 Noviembre, 2003, 08:37 pm
Leído 4982 veces

dralbor68

  • Visitante
Vector A
{ 0, 1, 2, 3, 4, 5 }
Con estos elemento hay que realizar las combinaciones en este caso son combinaciones de 6 tomadas de 2, en total 15.
 
Vector B
vector:={4, 1, 0, 2, 4, 3, 1, 2, 4, 4, 3, 0, 5, 0, 5, 2, 3, 1, 5, 4, 0, 2, 1}
Es un vector totalmente aleatorio de datos del Vector A donde voy a buscar las combinaciones.
 
Combinaciones formadas con el Vector A
vector:={4, 1, 0, 2, 4, 3, 1, 2, 4, 4, 3, 0, 5, 0, 5, 2, 3, 1, 5, 4, 0, 2, 1}
            2  3           7             12    14          18       21    23
 
{ 0, 1 } = 2, 3, 7,12,14,18,21,23    Posiciones en donde aparecen alguno de los
                                     elementos de la primera combinación {0,1} en el
                                     Vector B.
                                     En el primer caso, el 2 indica que uno de los
                                     elementos de la primera combinación (0,1) del
                                     Vector A apareció en la posición 2 del Vector B.                                      
2, 1, 4, 5, 2, 4, 3, 2, 0            Diferencias de posiciones referidas anteriormente.
                                     Ej.: Pos.1(2-0=2), Pos.2(3-2=1), Pos.3(7-3=4),
                                     Pos.4(12-7=5), Pos.5(14-12=2), Pos.6(18-14=4), etc.
                                     La ultima diferencia da 0 debido a que el ultimo
                                     Numero del vector aleatorio es uno de los elementos
                                     de la primera combinatoria, entonces (Longitud del
                                     Vector – Ultima posición de la combinatoria) =
                                     Ultima diferencia, en este caso 23-23=0.
                                     Se busca el máximo resultado de estas diferencias,
                                     incluyendo a la ultima diferencia. En este caso es
                                     5, como se muestra en el ejemplo.

El mismo procedimiento se aplica para las demas combinatorias.
El primer renglón son la posiciones y el segundo las diferencias.
 
{ 0, 2 } =  3, 4, 8,12,14,16,21,22
            3, 1, 4, 4, 2, 2, 5, 1, 1
{ 0, 3 } =  3, 6,11,12,14,17,21
            3, 3, 5, 1, 2, 3, 4, 2
{ 0, 4 } =  1, 3, 5, 9,10,12,14,20,21
            1, 2, 2, 4, 1, 2, 2, 6, 1, 2
{ 0, 5 } =  3,12,13,14,15,19,21
            3, 9, 1, 1, 1, 4, 2, 2
{ 1, 2 } =  2, 4, 7, 8,16,18,22,23
            2, 2, 3, 1, 8, 2, 4, 1, 0
{ 1, 3 } =  2, 6, 7,11,17,18,23
            2, 4, 1, 4, 6, 1, 5, 0
{ 1, 4 } =  1, 2, 5, 7, 9,10,18,20,23
            1, 1, 3, 2, 2, 1, 8, 2, 3, 0
{ 1, 5 } =  2, 7,13,15,18,19,23
            2, 5, 6, 2, 3, 1, 4, 0
{ 2, 3 } =  4, 6, 8,11,16,17,22
            4, 2, 2, 3, 5, 1, 5, 1
{ 2, 4 } =  1, 4, 5, 8, 9,10,16,20,22
            1, 3, 1, 3, 1, 1, 6, 4, 2, 1
{ 2, 5 } =  4, 8,13,15,16,19,22
            4, 4, 5, 2, 1, 3, 3, 1
{ 3, 4 } =  1, 5, 6, 9,10,11,17,20
            1, 4, 1, 3, 1, 1, 6, 3, 3
{ 3, 5 } =  6,11,13,15,17,19
            6, 5, 2, 2, 2, 2, 4
{ 4, 5 } =  1, 5, 9,10,13,15,19,20
            1, 4, 4, 1, 3, 2, 4, 1, 3
 
Luego de esto se toma el menor de las mayores intervalos.
 
{ 0, 1 } = 2, 1, 4, 5, 2, 4, 3, 2, 0      Maximo intervalo: 5
{ 0, 2 } = 3, 1, 4, 4, 2, 2, 5, 1, 1      Maximo intervalo: 5
{ 0, 3 } = 3, 3, 5, 1, 2, 3, 4, 2         Maximo intervalo: 5
{ 0, 4 } = 1, 2, 2, 4, 1, 2, 2, 6, 1, 2   Maximo intervalo: 6
{ 0, 5 } = 3, 9, 1, 1, 1, 4, 2, 2         Maximo intervalo: 9
{ 1, 2 } = 2, 2, 3, 1, 8, 2, 4, 1, 0      Maximo intervalo: 8
{ 1, 3 } = 2, 4, 1, 4, 6, 1, 5, 0         Maximo intervalo: 6
{ 1, 4 } = 1, 1, 3, 2, 2, 1, 8, 2, 3, 0   Maximo intervalo: 8
{ 1, 5 } = 2, 5, 6, 2, 3, 1, 4, 0         Maximo intervalo: 6
{ 2, 3 } = 4, 2, 2, 3, 5, 1, 5, 1         Maximo intervalo: 5
{ 2, 4 } = 1, 3, 1, 3, 1, 1, 6, 4, 2, 1   Maximo intervalo: 6
{ 2, 5 } = 4, 4, 5, 2, 1, 3, 3, 2         Maximo intervalo: 5
{ 3, 4 } = 1, 4, 1, 3, 1, 1, 6, 3, 3      Maximo intervalo: 6
{ 3, 5 } = 6, 5, 2, 2, 2, 2, 4            Maximo intervalo: 6
{ 4, 5 } = 1, 4, 4, 1, 3, 2, 4, 1, 3      Maximo intervalo: 4
 
La combinatoria { 4, 5 } es la que tiene el intervalo minimo.
Puede darse casos en que sea mas de una combinatoria la resultante.
 
Con pocos números como podemos ver, el resultado es facil de hallar, pero en cuanto crece el entorno de numeros del vector A y la cantidad de datos del Vector B y se utilizan combinatorias de 9 o mas numeros, la obtención de los resultados requiere de mucho tiempo.
La pregunta es:
Existe alguna forma de obtener esto fácilmente con operaciones matemáticas ?. por ejemplo operación de vectores o matrices ?
 
Le solicito que si hay alguna forma me lo haga saber.
Desde ya muchas Gracias.
 
Daniel Albornoz