Buscar conjunto de números en una colección que se suma a un número en otra

Question

Para un juego que estoy haciendo Tengo una situación en la que tengo una lista de números – dice [7, 4, 9, 1, 15, 2 ] (llamado A para esto) – y otra lista de números – dice [11, 18, 14, 8, 3] (llamado B) – me fue proporcionado. El objetivo es encontrar todas las combinaciones de números en A que se suman a un número en B. Por ejemplo:

• 1 + 2 = 3
• 1 + 7 = 8
• 2 + 9 = 11
• 4 + 7 = 11
• 1 + 2 + 4 + 7 = 14
• 1 + 2 + 15 = 18
• 2 + 7 + 9 = 18

... y así sucesivamente. (Para este propósito, 1 + 2 es lo mismo que 2 + 1.)

Para listas pequeñas como esta, es trivial simplemente usar fuerza bruta en las combinaciones, pero estoy enfrentando la posibilidad de ver miles a decenas de miles de estos números y usará esta rutina repetidamente a lo largo de la vida útil de la aplicación. ¿Hay algún tipo de algoritmo elegante disponible para lograr esto en un tiempo razonable con una cobertura del 100%? En su defecto, ¿hay algún tipo de heurística decente que pueda encontrar que pueda darme un conjunto "lo suficientemente bueno" de combinaciones en un tiempo razonable?

Estoy buscando un algoritmo en pseudo-código o en cualquier lenguaje bastante popular y legible (tenga en cuenta el "y" allí ....;) o incluso una descripción en inglés de cómo se implementaría esto tipo de búsqueda.

---

Editado para añadir:

montón de buena información proporcionada hasta el momento. ¡Gracias amigo! Resumiendo por ahora:

• El problema es NP-Completo, por lo que no hay forma de obtener la fuerza bruta para obtener el 100% de precisión en un tiempo razonable.
• El problema se puede ver como una variante de los problemas subset sum o knapsack. Existen heurísticas bien conocidas para ambos que pueden ser adaptables a este problema.

¡Que sigan las ideas! ¡Y gracias de nuevo!

Answer 1

Este problema es NP-Completo ... Esta es una variación del problema de la suma de subconjuntos que se sabe que es NP-Completo (en realidad, el problema de la suma de subconjuntos es más fácil que el suyo)

Lea aquí para obtener más información: http://en.wikipedia.org/wiki/Subset_sum_problem

Answer 2

suena como un problema de la mochila (ver http://en.wikipedia.org/wiki/Knapsack_problem. En esa página también explican que el problema es NP-completo en general.

Creo que esto significa que si usted quiere encontrar todas las combinaciones válidas, sólo tiene mucho tiempo.

Answer 3

Esta es una pequeña generalización del subset sum problem. En general, es NP-completo, pero mientras todos los números sean enteros y el número máximo en B sea relativamente pequeño, la solución pseudopolinómica descrita en el artículo de Wikipedia que relacioné debería ser la solución.

Answer 4

Como se dijo en los comentarios con números que van del 1 al 30, el problema tiene una solución rápida. Lo probé en C y para su ejemplo dado solo necesita milisegundos y se escalará muy bien. La complejidad es O (n + k) donde n es la longitud de la lista A yk la longitud de la lista B, pero con un factor constante alto (hay 28.598 posibilidades de obtener una suma de 1 a 30).

#define WIDTH 30000 
#define MAXNUMBER 30 

int create_combination(unsigned char comb[WIDTH][MAXNUMBER+1], 
         int n, 
         unsigned char i, 
         unsigned char len, 
         unsigned char min, 
         unsigned char sum) { 
    unsigned char j; 

    if (len == 1) { 
     if (n+1>=WIDTH) { 
      printf("not enough space!\n"); 
      exit(-1); 
     } 
     comb[n][i] = sum; 
     for (j=0; j<=i; j++) 
      comb[n+1][j] = comb[n][j]; 
     n++; 
     return n; 
    } 

    for (j=min; j<=sum/len; j++) { 
     comb[n][i] = j; 
     n = create_combination(comb, n, i+1, len-1, j, sum-j); 
    } 

    return n; 
} 

---

int main(void) 
{ 
    unsigned char A[6] = { 7, 4, 9, 1, 15, 2 }; 
    unsigned char B[5] = { 11, 18, 14, 8, 3 }; 

    unsigned char combinations[WIDTH][MAXNUMBER+1]; 
    unsigned char needed[WIDTH][MAXNUMBER]; 
    unsigned char numbers[MAXNUMBER]; 
    unsigned char sums[MAXNUMBER]; 
    unsigned char i, j, k; 
    int n=0, m; 

    memset(combinations, 0, sizeof combinations); 
    memset(needed, 0, sizeof needed); 
    memset(numbers, 0, sizeof numbers); 
    memset(sums, 0, sizeof sums); 

    // create array with all possible combinations 
    // combinations[n][0] stores the sum 
    for (i=2; i<=MAXNUMBER; i++) { 
     for (j=2; j<=i; j++) { 
      for (k=1; k<=MAXNUMBER; k++) 
       combinations[n][k] = 0; 
      combinations[n][0] = i; 
      n = create_combination(combinations, n, 1, j, 1, i); 
     } 
    } 

    // count quantity of any summands in each combination 
    for (m=0; m<n; m++) 
     for (i=1; i<=MAXNUMBER && combinations[m][i] != 0; i++) 
      needed[m][combinations[m][i]-1]++; 

    // count quantity of any number in A 
    for (m=0; m<6; m++) 
     if (numbers[A[m]-1] < MAXNUMBER) 
      numbers[A[m]-1]++; 

    // collect possible sums from B 
    for (m=0; m<5; m++) 
     sums[B[m]-1] = 1; 

    for (m=0; m<n; m++) { 
     // check if sum is in B 
     if (sums[combinations[m][0]-1] == 0) 
      continue; 

     // check if enough summands from current combination are in A 
     for (i=0; i<MAXNUMBER; i++) { 
      if (numbers[i] < needed[m][i]) 
       break; 
     } 

     if (i<MAXNUMBER) 
      continue; 

     // output result 
     for (j=1; j<=MAXNUMBER && combinations[m][j] != 0; j++) { 
      printf(" %s %d", j>1 ? "+" : "", combinations[m][j]); 
     } 
     printf(" = %d\n", combinations[m][0]); 
    } 

    return 0; 
} 

---

1 + 2 = 3 
1 + 7 = 8 
2 + 9 = 11 
4 + 7 = 11 
1 + 4 + 9 = 14 
1 + 2 + 4 + 7 = 14 
1 + 2 + 15 = 18 
2 + 7 + 9 = 18