¿Qué técnica utilizo para cuando quiero verificar todas las combinaciones posibles de un conjunto?

Question

estoy trabajando a través de una pregunta de la entrevista que dice así:

Dada una matriz de enteros y suma, comprobación de si cualquier combinación suma a la suma.

¿Qué técnica de programación utiliza uno cuando quiere probar todas las combinaciones posibles de un conjunto?

Incluso si esa no es la mejor solución a este problema, me encuentro con problemas donde necesito generar o hacer algo con todas las combinaciones de una lista, y me gustaría saber cómo manejar eso.

Answer 1

Una visión práctica es darse cuenta de que la representación binaria de los números del 0 a (2^N)-1 es en realidad un conjunto de máscaras de bits para las combinaciones posibles de cada N artículos distintos. Por ejemplo, para N=3 (3 artículos) y por lo tanto (2^3)-1 = 7:

0: 000 = none 
1: 001 = third item 
2: 010 = second item 
3: 011 = second and third items 
4: 100 = first item 
5: 101 = first and third items 
6: 110 = first and second items 
7: 111 = all 3 items 

Esto hace que sea muy fácil de bucle a través de todas las selecciones posibles en un orden establecido (por lo que es imposible para saltar o doble visitar cualquier selección potencial) .

Answer 2

Recursivamente. El pseudocódigo sería algo como esto:

function f(set,currentelement,selectedelements,sum,wantedsum) 
{ 
for (thiselement=currentelement+1 to lastelement) 
    { 
    if (sum+thiselement==wantedsum) print out selectedelements+thiselement; 
    if (sum+thiselement<wantedsum) 
     { 
     f(set,thiselement,selectedelements+thiselement,sum+thiselement,wantedsum); 
     } 
    } 

Answer 3

Aquí se necesita cierta atención con la terminología. Combinaciones se usa para referirse a la selección de artículos de k de un conjunto de n artículos, donde el orden de los artículos k no es relevante. El concepto relacionado de elegir k elementos de un conjunto de n artículos, donde el orden de k artículos hace materia, se conoce como permutación.

Lo que se habla acerca de un principio, sin embargo:

Dada una matriz de enteros y suma, comprobar si cualquier combinación se suma a la suma.

es una cosa diferente - aquí no hay ningún k fijo: usted está interesado en cualquier subconjunto de tamaño de los artículos originales.

El conjunto de todos los subconjuntos de un conjunto S se llama conjunto de potencia de S, y hay una fórmula muy simple para la cantidad de miembros que contiene. Lo dejo como un ejercicio: una vez que lo haya resuelto, debería ser relativamente obvio cómo enumerar a través de los miembros del conjunto de poder de un conjunto.

(Pista: el poder-conjunto de { 1, 2 } es { {}, { 1 }, { 2 }, { 1, 2 } })

Answer 4

Eso suena como un problema de recursividad clásico. Empiezas con el primer elemento y consideras el resto de la matriz; para cada elemento, ya sea que se elija o no. El caso base es cuando el índice de inicio es mayor que la longitud de la matriz.Algo así como

public static bool canSum(int start, int[] array, int sum) 
{ 
     if (start >= array.Length) 
      return sum == 0; 
     return canSum(start + 1, array, sum - array[start]) || canSum(start + 1, array, sum); 
} 

Answer 5

Si tiene números enteros positivos y negativos, que se va a ejecutar en una explosión combinatoria, donde cualquier algoritmo que elija va a reducir la velocidad en un porcentaje fijo por cada aumento en la longitud de la matriz. (Si solo tiene números enteros positivos, puede enlazar su búsqueda una vez que se exceda la suma objetivo).

Una pregunta límite: ¿puede reutilizar enteros también?

Debe buscar 'algoritmos combinatorios'. Knuths 'tome-in-progress podría ayudarlo bastante si quiere profundizar en la cuestión.

Answer 6

veo dos opciones:

1. calcular el conjunto de alimentación de la matriz de entrada y comprobar la suma de cada elemento en el conjunto de alimentación (consulte http://en.wikipedia.org/wiki/Power_set). Esto es probablemente O (2^N) y no es bueno para grandes N
2. Pruebe algo con el problema 0-1 Knapsack (consulte http://en.wikipedia.org/wiki/Knapsack_problem). Esto debería encontrar la suma más grande menor que su valor deseado, una suma que es su valor deseado, o no encontrar nada. Según el resultado, puede responder a su pregunta original. 0-1 Knapsack es bueno porque se ejecuta en tiempo polinomial O (N^c) donde c es constante. Sin embargo, no recuerdo si funciona para números negativos.

Answer 7

Esto no responde a su pregunta "combinación", pero es probablemente la solución óptima a la pregunta: P

Este es el subconjunto sum problem problema en el que usted tiene que buscar N sumas.

suma de subconjuntos tiene un algoritmo de pseudo polinomio utilizando programación dinámica:

psuedocode de esta link

Subset-Sum-Solver[S = w1,w2, . . . ,wn,B] 
1 Initialize M[0..n, 0..B] everywhere False apart from M[0, 0] = True 
2 for i from 1 to n 
    do 
3 for w from 0 to B 
    do 
4  M[i,w] = M[i − 1,w] _M[i − 1,w − wi] 
     (any reference outside the array returns false) 
5 Output M[n,B] 

donde B es la suma, S es el conjunto de números, n es la cardinalidad de S (número de elementos en S), y M es una matriz de B. Este algoritmo es O (nB)

En el caso de la pregunta de la entrevista, haga esto para cada suma, y ​​obtendrá un algoritmo que es O (nmB) donde m es el número de sumas que debe probar.

La pregunta es un poco ambigua, ¿la matriz de enteros utilizada para obtener subconjuntos también tiene el mismo conjunto de sumas? es decir, ¿un subconjunto de enteros en la matriz A también se suma a uno de los enteros en la matriz A? en ese caso, entonces el algoritmo es O (n^2B) ya que n == m

Answer 8

Si elige calcular un powerset, se puede hacer bastante fácilmente de una manera funcional.

En Haskell, hay funciones de subsequences que esencialmente devuelve el conjunto de potencias de cualquier conjunto, como una lista de listas.

O puede escribir usted mismo

powerSet :: [a] -> [[a]] 
powerSet [] = [[]] 
powerSet x:xs = map (:x) (powerSet xs) ++ (powerSet xs) 

Answer 9

Hay varias maneras de resolver este problema. Una es la clásica solución DP que otros han publicado.Voy a publicar una solución que usa solo memoria O (S), donde S es la suma de todos los enteros en la matriz (se puede cambiar para significar la suma deseada también) y otra que usa un algoritmo aleatorizado muy eficiente que puede ser probado para ser muy rápido incluso para cientos de miles de números de cualquier tamaño, e incluso números racionales y negativos.

solución de DP en tiempo O (NS) y la memoria O (S):

//let F[i] = 1 if we can get sum i and 0 otherwise 
F[0] = 1; // we can always make sum 0 
for (int i = 1; i <= n; ++i) 
    for (int j = S; j >= numbers[i]; --j) 
    F[j] |= F[j - numbers[i]]; // basically, if F[j - numbers[i]] == 1, then we 
           // can add numbers[i] to make F[j] 1, otherwise 
           // we can't. A bitwise or operation will save us 
           // an if/else structure basically. 

Pseudocódigo para el algoritmo aleatorio: Let utilizadas = lista de números a los que suma. Let Unused = lista de números que NO sumas. Dejar tmpsum = 0. Deje que S = suma deseada que desea alcanzar.

for (each number x you read) 
    toss a coin: 
    if it's heads and tmpsum < S 
     add x to Used 
    else 
     add x to Unused 

while (tmpsum != S) 
    if tmpsum < S 
    MOVE one random number from Unused to Used 
    else 
    MOVE one random number from Used to Unused 

print the Used list, containing the numbers you need to add to get S 

Esto será mucho más rápido que la solución de programación dinámica, especialmente para las entradas aleatorias. Los únicos problemas son que no puede detectar de manera confiable cuando no hay solución (puede dejar que el algoritmo se ejecute durante unos segundos y, si no termina, asumir que no hay solución) y que no puede estar seguro de que obtendrá la solución con el mínimo número de elementos elegidos. De nuevo, podría agregar algo de lógica para hacer que el algoritmo continúe e intente encontrar una solución con menos elementos hasta que se cumplan ciertas condiciones de detención, pero esto lo hará más lento. Sin embargo, si solo está interesado en una solución que funciona y tiene MUCHOS números y la suma deseada puede ser MUY grande, probablemente sea mejor que el algoritmo DP.

Otra ventaja de este enfoque es que también funcionará para números negativos y racionales sin modificaciones, lo que no es cierto para la solución DP, porque la solución DP implica el uso de sumas parciales como índices de matriz, y los índices solo pueden ser números naturales. Por supuesto, puede usar hashtables, pero eso hará que la solución DP sea aún más lenta.

para generar todas las combinaciones, usted debe mirar hacia arriba dando marcha atrás: http://en.wikipedia.org/wiki/Backtracking

Para este problema, es necesario utilizar algo como esto:

void back(int k) 
{ 
    if (k > numElements) 
    { 
    // add all the nums[i] for which st[i] == 1 and check 
    // if their sum is what you desire, then return; 
    } 

    for (int i = 0; i <= 1; ++i) 
    { 
    st[k] = i; 
    back(k + 1); 
    } 
} 

debería ejecutar en un papel de pequeño número de elementos para ver cómo funciona Puede optimizarlo calculando la suma sobre la marcha, evitando así la suma final. Esta es la idea general.