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

Question

Para un juego que estoy haciendo Tengo una situación en la que tengo una lista de números - por ejemplo [7, 4, 9, 1, 15, 2] (A llamado para esto) - y otra lista de los números - por ejemplo [11, 18, 14, 8, 3] (B llamado) - proporcionan a mí. 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 propósitos de esta, 1 + 2 es el mismo que 2 + 1.)

Para las pequeñas listas como esta, es trivial simplemente por fuerza bruta las combinaciones, pero estoy frente a la posibilidad de ver a miles a decenas de miles de estos números y se utiliza esta rutina en repetidas ocasiones durante la vida útil de la aplicación. ¿Hay algún tipo de algoritmo elegante disponibles para lograr esto en un tiempo razonable, con una cobertura del 100%? De no ser así, ¿hay algún tipo de heurística decente que puedo encontrar que me puede dar un conjunto "suficientemente bueno" de combinaciones en un período razonable de tiempo?

Estoy buscando un algoritmo en pseudocódigo o en cualquier idioma decentemente popular y legible (nótese el "y" no ....;) o incluso sólo una descripción de Inglés cómo se podría ir sobre la implementación de este tipo de búsqueda.

---

Editado para añadir:

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

• El problema es NP-completo lo que no hay camino corto de la fuerza bruta para obtener el 100% de precisión en un tiempo razonable.
• El problema puede ser vista como una variante de cualquiera de los subconjunto resumir o mochila problemas "noreferrer". Hay heurística bien conocidos para tanto que puede ser adaptable a este problema.

seguir viniendo las ideas! Y gracias de nuevo!

Answer 1

Este problema es NP-completo ... Esta es una variación del problema de la suma subconjunto de los que se sabe que es NP-completo (en realidad, el problema de la suma de sub-conjunto es más fácil que la suya).

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

Answer 2

Como se dijo en los comentarios con números que van solamente de 1 a 30 el problema tiene una solución rápida. Lo he comprobado en C y por su ejemplo dado que sólo necesita milisegundos y se escala muy bien. La complejidad es O (n + k), donde n es la longitud de lista A y k la longitud de lista B, pero con un alto factor constante (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

Answer 3

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 se necesita un montón de tiempo.

Answer 4

Esta es una pequeña generalización de la subconjunto suma problema . En general, es NP-completo, pero siempre y cuando todos los números son enteros y el número máximo de B es relativamente pequeño, la solución pseudo-polinomial se describe en el artículo de Wikipedia he vinculado debe hacer el truco.