¿Algún algoritmo para encontrar un par de sumas de una lista de números?

Question

Supongamos que tiene la siguiente lista de números, {3,6,10,9,13,16,19}, no necesariamente en ese orden. Ahora, sin saber que este es el conjunto de la combinación posible del conjunto {3,6,10}, existe un algoritmo, en cualquier lenguaje de programación que pueda usarse para encontrar estas combinaciones de manera eficiente. Básicamente, quiero recuperar la lista del conjunto total, donde se incluyen todos los números. ¿Qué es un algoritmo eficiente, no deseo reinventar la rueda si ya existe?

Answer 1

Para el caso general donde puede haber cualquier número de elementos, aquí es un (q * log (q)) algoritmo O donde q es el tamaño de la lista de entrada:

1. Ordenar la lista q en orden ascendente.
2. Elimina el elemento más pequeño, m, y añádelo al conjunto de resultados. Eliminarlo de q.
3. Iterar sobre q. Mantenga una lista de números que hemos visto. Si vemos un número que es (un número que ya hemos visto + m), entonces deséchelo. Esto debería mantener la mitad de los números (todos los que no implican m).
4. Repita desde el paso 2 hasta que se encuentren todos los números.

Aquí es una implementación de este algoritmo en Python:

def solve(q): 
    q = sorted(q) 
    x = [] 
    while q: 
     x.append(q[0]) 

     s = [False]*len(q) 
     s[0] = True 
     j = 1 

     for i in range(1, len(q)): 
      if q[i] == q[0] + q[j]: 
       s[i] = True 
       j += 1 
       while j < len(q) and s[j]: 
        j += 1 

     q = [k for k, v in zip(q, s) if not v] 
    return x 

s = [1, 3, 7, 12, 13, 20, 25, 31, 32, 33, 62, 78, 80, 92, 99] 
from itertools import combinations 
q = list(sum(x) for r in range(1, len(s) + 1) for x in combinations(s, r)) 
print(solve(q)) 

Resultado:

[1, 3, 7, 12, 13, 20, 25, 31, 32, 33, 62, 78, 80, 92, 99] 

---

Respuesta original:

Suponiendo que sólo hay 3 números en el lista, y que ningún número puede ser negativo:

Dos de los números deben ser los dos números más pequeños de la lista. El número más grande debe ser la suma de los tres. Por sustracción puedes encontrar el tercer número.

Answer 2

1) Encuentre los dos números más pequeños, estos deben ser parte de la lista original.

2) Encuentre su suma, todo lo más pequeño en la lista debe ser parte de la lista original.

3) Encuentre la siguiente suma más pequeña y repita hasta que se completen todas las sumas de dos números.

Cada vez que agrega un número a la lista original o encuentra una suma, elimínela de la lista grande.

4) Continúe con 3 sumas numéricas, y siga aumentando hasta que la lista grande esté vacía.

Editar:

Encontrar la siguiente suma más pequeña requiere una lista ordenada de los números. Si su lista es A, B, C, D, E, entonces la suma más pequeña es A + B y la siguiente suma más pequeña es A + C.

La interpretación es tan terrible como puede ser: 2^N, pero si estoy leyendo su pregunta correctamente, la lista contiene su lista original y todas las sumas posibles, lo que le permitiría aumentar el rendimiento considerablemente.

Por ejemplo, usted sabe cuántos números está buscando, lo que significa que sabe cuando solo necesita uno más, y como también conoce el número más grande de la lista, el último número es el número más grande menos todos los números ya se ha agregado a tu lista original.

Answer 3

Esta es la forma de hacerlo. O al menos es una solución ingenua.

En primer lugar usted pide los números en orden ascendente. Suponiendo que A es la lista de resultados ordenados y S es el conjunto de números mínimos a partir de los cuales puede construir A.

Pasar por A. Si no existe un subconjunto de S que se suma a _i agregue un nuevo número a S tal que lo hace.

En la primera iteración Esto añadirá min (A). El segundo número probablemente esté en S. Esto es bastante intensivo desde el punto de vista computacional porque para cada número que examine en A deberá asegurarse de que exista un subconjunto de S que lo agregue y que no agregue un número eso crea un subconjunto de S que agrega algo en A.

Puede optimizar esto un poco, cada vez que agrega un número a S, calcula todas las sumas posibles incluyendo ese nuevo elemento y quitándoselos de A. Mantenga yendo hasta vaciar A.

Se complica si los números pueden ser negativos, pero verá esto porque tendrá que haber un elemento negativo de A para que esto sea posible.