python - sumatoria - Algoritmo para encontrar qué número en una lista suma hasta cierto número

sumar los numeros del 1 al 100 python

Question

Tengo una lista de números. También tengo una cierta suma. La suma se hace a partir de unos pocos números de mi lista (es posible / no puedo saber de cuántos números están hechos). ¿Hay un algoritmo rápido para obtener una lista de números posibles? Escrito en Python sería genial, pero el pseudocódigo también es bueno. (Todavía no puedo leer nada que no sea Python: P)

Ejemplo

list = [1,2,3,10]
sum = 12
result = [2,10]

NOTA: Sé de Algoritmo para encontrar qué números de una lista de tamaño n suman a otro número (pero no puedo leer C # y no puedo verificar si funciona para mis necesidades. Estoy en Linux y traté de usar Mono, pero me dan errores y no puedo entender cómo trabajar C # :(
Y sí conozco un algoritmo para resumir una lista de números para todas las combinaciones (pero parece ser bastante ineficiente. No necesito todas las combinaciones).

Answer 1

Entonces, la lógica es revertir la ordenación de los números, y supongamos que la lista de números es l y la suma a formar es s .

   for i in b:
            if(a(round(n-i,2),b[b.index(i)+1:])):
                r.append(i)    
                return True
        return False

luego, pasamos por este bucle y seleccionamos un número de l en orden y digamos que es i . Hay 2 casos posibles: i es la parte de la suma o no. Entonces, asumimos que i es parte de la solución y luego el problema se reduce a l ser l[l.index(i+1):] y s ser si , si nuestra función es a (l, s) entonces llamamos a(l[l.index(i+1):] ,si) . y si i no es parte de s, entonces debemos formar s desde la lista l[l.index(i+1):] . Así que es similar en ambos casos, solo el cambio es si i es parte de s, entonces s = si y de lo contrario s = s solo.

Ahora, para reducir el problema, en el caso de que los números en l sean mayores que s, los eliminamos para reducir la complejidad hasta que esté vacío y, en ese caso, los números seleccionados no forman parte de nuestra solución y devolvemos el valor falso.

if(len(b)==0):
    return False    
while(b[0]>n):
    b.remove(b[0])
    if(len(b)==0):
        return False    

y en el caso de que le quede solo 1 elemento, o bien puede ser parte de s, entonces devolvemos verdadero o no, entonces devolvemos falso y el bucle pasará por otro número.

if(b[0]==n):
    r.append(b[0])
    return True
if(len(b)==1):
    return False

note en el bucle si he usado b..but b solo en nuestra lista. Y lo he redondeado siempre que sea posible, para que no obtengamos una respuesta incorrecta debido a los cálculos de punto flotante en python.

r=[]
list_of_numbers=[61.12,13.11,100.12,12.32,200,60.00,145.34,14.22,100.21,14.77,214.35,200.32,65.43,0.49,132.13,143.21,156.34,11.32,12.34,15.67,17.89,21.23,14.21,12,122,134]
list_of_numbers=sorted(list_of_numbers)
list_of_numbers.reverse()
sum_to_be_formed=401.54
def a(n,b):
    global r
    if(len(b)==0):
        return False    
    while(b[0]>n):
        b.remove(b[0])
        if(len(b)==0):
            return False    
    if(b[0]==n):
        r.append(b[0])
        return True
    if(len(b)==1):
        return False
    for i in b:
        if(a(round(n-i,2),b[b.index(i)+1:])):
            r.append(i)    
            return True
    return False
if(a(sum_to_be_formed,list_of_numbers)):
    print(r)

Esta solución funciona más rápido. Más rápido que uno explicado anteriormente. Sin embargo, esto funciona solo para números positivos. Sin embargo, también funciona bien si hay una solución, de lo contrario, lleva mucho tiempo salir de los bucles.

un ejemplo de ejecución es como esto, digamos

    l=[1,6,7,8,10]

and s=22 i.e. s=1+6+7+8
so it goes through like this 

1.) [10, 8, 7, 6, 1] 22
i.e. 10  is selected to be part of 22..so s=22-10=12 and l=l.remove(10)
2.) [8, 7, 6, 1] 12
i.e. 8  is selected to be part of 12..so s=12-8=4 and l=l.remove(8)
3.) [7, 6, 1] 4  
now 7,6 are removed and 1!=4 so it will return false for this execution where 8 is selected.
4.)[6, 1] 5
i.e. 7  is selected to be part of 12..so s=12-7=5 and l=l.remove(7)
now 6 are removed and 1!=5 so it will return false for this execution where 7 is selected.
5.)[1] 6
i.e. 6  is selected to be part of 12..so s=12-6=6 and l=l.remove(6)
now 1!=6 so it will return false for this execution where 6 is selected.
6.)[] 11
i.e. 1 is selected to be part of 12..so s=12-1=1 and l=l.remove(1)
now l is empty so all the cases for which 10 was a part of s are false and so 10 is not a part of s and we now start with 8 and same cases follow.
7.)[7, 6, 1] 14
8.)[6, 1] 7
9.)[1] 1

Solo para dar una comparación que ejecuté en mi computadora que no es tan buena. utilizando

l=[61.12,13.11,100.12,12.32,200,60.00,145.34,14.22,100.21,14.77,214.35,145.21,123.56,11.90,200.32,65.43,0.49,132.13,143.21,156.34,11.32,12.34,15.67,17.89,21.23,14.21,12,122,134]

y

s = 2000

Mi bucle corrió 1018 veces y 31 ms.

y el bucle de código anterior corrió 3415587 veces y tomó cerca de 16 segundos.

sin embargo, en caso de que no exista una solución, mi código se ejecutó durante más de unos pocos minutos, por lo que lo detuve y el código anterior se ejecutó cerca de solo 17 ms y el código anterior también funciona con números negativos.

Así que creo que se pueden hacer algunas mejoras.

Answer 2

Este problema se reduce al problema de mochila 0-1 , donde está tratando de encontrar un conjunto con una suma exacta. La solución depende de las restricciones, en el caso general este problema es NP-Complete.

Sin embargo, si la suma máxima de búsqueda (llamémosla S ) no es demasiado alta, entonces puede resolver el problema utilizando la programación dinámica. Lo explicaré utilizando una función recursiva y una memoization , que es más fácil de entender que un enfoque de abajo hacia arriba.

Codifiquemos una función f(v, i, S) , de manera que devuelva el número de subconjuntos en v[i:] que se suma exactamente a S Para resolverlo recursivamente, primero tenemos que analizar la base (es decir, v[i:] está vacío):

• S == 0: el único subconjunto de [] tiene la suma 0, por lo que es un subconjunto válido. Debido a esto, la función debe devolver 1.

• S! = 0: Como el único subconjunto de [] tiene la suma 0, no hay un subconjunto válido. Debido a esto, la función debe devolver 0.

Luego, analicemos el caso recursivo (es decir, v[i:] no está vacío). Hay dos opciones: incluir el número v[i] en el subconjunto actual, o no incluirlo. Si incluimos v[i] , entonces estamos buscando subconjuntos que tienen la suma S - v[i] , de lo contrario, todavía estamos buscando subconjuntos con la suma S La función f podría implementarse de la siguiente manera:

def f(v, i, S):
  if i >= len(v): return 1 if S == 0 else 0
  count = f(v, i + 1, S)
  count += f(v, i + 1, S - v[i])
  return count

v = [1, 2, 3, 10]
sum = 12
print(f(v, 0, sum))

Al marcar f(v, 0, S) > 0 , puede saber si hay una solución a su problema. Sin embargo, este código es demasiado lento, cada llamada recursiva genera dos llamadas nuevas, lo que lleva a un algoritmo O (2 ^ n). Ahora, podemos aplicar la memoization para que se ejecute en el tiempo O (n * S), que es más rápido si S no es demasiado grande:

def f(v, i, S, memo):
  if i >= len(v): return 1 if S == 0 else 0
  if (i, S) not in memo:  # <-- Check if value has not been calculated.
    count = f(v, i + 1, S, memo)
    count += f(v, i + 1, S - v[i], memo)
    memo[(i, S)] = count  # <-- Memoize calculated result.
  return memo[(i, S)]     # <-- Return memoized value.

v = [1, 2, 3, 10]
sum = 12
memo = dict()
print(f(v, 0, sum, memo))

Ahora, es posible codificar una función g que devuelve un subconjunto que suma S Para hacer esto, es suficiente agregar elementos solo si hay al menos una solución que los incluya:

def f(v, i, S, memo):
  # ... same as before ...

def g(v, S, memo):
  subset = []
  for i, x in enumerate(v):
    # Check if there is still a solution if we include v[i]
    if f(v, i + 1, S - x, memo) > 0:
      subset.append(x)
      S -= x
  return subset

v = [1, 2, 3, 10]
sum = 12
memo = dict()
if f(v, 0, sum, memo) == 0: print("There are no valid subsets.")
else: print(g(v, sum, memo))

Descargo de responsabilidad: esta solución dice que hay dos subconjuntos de [10, 10] que suman 10. Esto se debe a que supone que los diez primeros son diferentes a los diez segundos. El algoritmo se puede arreglar para suponer que ambas decenas son iguales (y por lo tanto responden a una), pero eso es un poco más complicado.

Answer 3

He encontrado una respuesta que tiene la complejidad de tiempo de ejecución O (n) y la complejidad de espacio sobre O (2n), donde n es la longitud de la lista.

La respuesta satisface las siguientes restricciones:

1. La lista puede contener duplicados, por ejemplo, [1,1,1,2,3] y desea encontrar la suma de los pares en 2

2. La lista puede contener enteros positivos y negativos

El código es el siguiente, y seguido por la explicación:

def countPairs(k, a):
    # List a, sum is k
    temp = dict()
    count = 0
    for iter1 in a:
        temp[iter1] = 0
        temp[k-iter1] = 0
    for iter2 in a:
        temp[iter2] += 1
    for iter3 in list(temp.keys()):
        if iter3 == k / 2 and temp[iter3] > 1:
            count += temp[iter3] * (temp[k-iter3] - 1) / 2
        elif iter3 == k / 2 and temp[iter3] <= 1:
            continue
        else:
            count += temp[iter3] * temp[k-iter3] / 2
    return int(count)

1. Cree un diccionario vacío, itere a través de la lista y ponga todas las claves posibles en el dict con un valor inicial 0. Tenga en cuenta que la clave (k-iter1) es necesaria para especificar, por ejemplo, si la lista contiene 1 pero no contiene 4, y la suma es 5. Luego, cuando miramos el 1, nos gustaría saber cuántos 4 tenemos, pero si 4 no está en el dictado, se generará un error.
2. Vuelva a repetir la lista y cuente cuántas veces ocurre cada entero y almacene los resultados en el dict.

3. Iterar a través del dict, esta vez es para encontrar cuántos pares tenemos. Necesitamos considerar 3 condiciones:

   3.1 La clave es solo la mitad de la suma y esta clave aparece más de una vez en la lista, por ejemplo, la lista es [1,1,1], la suma es 2. Tratamos esta condición especial como lo hace el código.

   3.2 La clave es solo la mitad de la suma y esta clave aparece solo una vez en la lista, omitimos esta condición.

   3.3 Para otros casos, esa clave no es la mitad de la suma, simplemente multiplique su valor por el valor de otra clave donde estas dos claves se suman al valor dado. Por ejemplo, si la suma es 6, multiplicamos temp [1] y temp [5], temp [2] y temp [4], etc ... (No enumeré los casos donde los números son negativos, pero la idea es la misma. )

El paso más complejo es el paso 3, que consiste en buscar en el diccionario, pero como la búsqueda en el diccionario es generalmente rápida, de complejidad casi constante. (Aunque el caso más desfavorable es O (n), pero no debería suceder con las teclas de enteros). Por lo tanto, si asumimos que la búsqueda es de complejidad constante, la complejidad total es O (n), ya que solo repetimos la lista por separado.

Se agradece consejo para una mejor solución :)

Answer 4

#!/usr/bin/python2

ylist = [1, 2, 3, 4, 5, 6, 7, 9, 2, 5, 3, -1]
print ylist 
target = int(raw_input("enter the target number")) 
for i in xrange(len(ylist)):
    sno = target-ylist[i]
    for j in xrange(i+1, len(ylist)):
        if ylist[j] == sno:
            print ylist[i], ylist[j]

Este código de Python hace lo que usted pidió, imprimirá el par único de números cuya suma es igual a la variable objetivo.

if target number is 8, it will print: 1 7 2 6 3 5 3 5 5 3 6 2 9 -1 5 3