eliminar números de una lista sin cambiar la suma total

Question

Tengo una lista de números (ejemplo: [-1, 1, -4, 5]) y tengo que eliminar los números de la lista sin cambiar la suma total de la lista. Quiero eliminar los números con el mayor valor absoluto posible, sin cambiar el total, en el ejemplo que elimina [-1, -4, 5] saldrá [1] por lo que la suma no cambia.

Escribí el enfoque ingenuo, que es encontrar todas las combinaciones posibles que no cambian el total y ver cuál elimina el mayor valor absoluto. Pero eso es realmente lento, ya que la lista real será mucho más grande que eso.

Aquí está mi código de combinaciones:

from itertools import chain, combinations 

def remove(items): 
    all_comb = chain.from_iterable(combinations(items, n+1) 
            for n in xrange(len(items))) 
    biggest = None 
    biggest_sum = 0 
    for comb in all_comb: 
     if sum(comb) != 0: 
      continue # this comb would change total, skip 
     abs_sum = sum(abs(item) for item in comb) 
     if abs_sum > biggest_sum: 
      biggest = comb 
      biggest_sum = abs_sum 
    return biggest 

print remove([-1, 1, -4, 5]) 

Se imprime corectly (-1, -4, 5). Sin embargo, estoy buscando alguna solución inteligente y más eficiente que el bucle sobre todas las combinaciones de elementos posibles.

¿Alguna idea?

Answer 1

si redefine el problema como encontrar un subconjunto cuya suma es igual al valor del conjunto completo, se dará cuenta de que este es un problema NP-duro, (subset sum)

lo que no hay solución de complejidad polinómica de este problema .

Answer 2

No programo en Python así que me disculpo por no ofrecer el código. Pero creo que puedo ayudar con el algoritmo:

1. encontrar la suma
2. añadir números con el valor más bajo hasta llegar a la misma suma
3. Todo lo demás se puede eliminar

I Espero que esto ayude

Answer 3

Sus requisitos no dicen si la función puede cambiar el orden de la lista o no. Aquí hay una posibilidad:

def remove(items): 
    items.sort() 
    running = original = sum(items) 
    try: 
     items.index(original) # we just want the exception 
     return [original] 
    except ValueError: 
     pass 
    if abs(items[0]) > items[-1]: 
     running -= items.pop(0) 
    else: 
     running -= items.pop() 
    while running != original: 
     try: 
      running -= items.pop(items.index(original - running)) 
     except ValueError: 
      if running > original: 
       running -= items.pop() 
      elif running < original: 
       running -= items.pop(0) 
    return items 

Este ordena la lista (grandes artículos estarán al final, los más pequeños estarán al principio) y calcula la suma, y ​​elimina un elemento de la lista. Luego continúa eliminando elementos hasta que el nuevo total sea igual al total original. Una versión alternativa que preserva el orden se puede escribir como un envoltorio:

from copy import copy 

def remove_preserve_order(items): 
    a = remove(copy(items)) 
    return [x for x in items if x in a] 

Aunque probablemente debería volver a escribir esto con collections.deque si realmente quiere preservar el orden. Si puede garantizar la exclusividad en su lista, puede obtener una gran ganancia utilizando un set en su lugar.

Probablemente podríamos escribir una mejor versión que atraviese la lista para encontrar los dos números más cercanos al total acumulado cada vez y eliminar el más cercano de los dos, pero probablemente terminaríamos con O (N^2) actuación. Creo que el rendimiento de este código será O (N * log (N)) ya que solo tiene que ordenar la lista (espero que la clasificación de la lista de Python no sea O (N^2)) y luego obtenga la suma.

Answer 4

#!/usr/bin/env python 
# -*- coding: utf-8 -*- 
# Copyright © 2009 Clóvis Fabrício Costa 
# Licensed under GPL version 3.0 or higher 

def posneg_calcsums(subset): 
    sums = {} 
    for group in chain.from_iterable(combinations(subset, n+1) 
            for n in xrange(len(subset))): 
     sums[sum(group)] = group 
    return sums 

def posneg(items): 
    positive = posneg_calcsums([item for item in items if item > 0]) 
    negative = posneg_calcsums([item for item in items if item < 0]) 
    for n in sorted(positive, reverse=True): 
     if -n in negative: 
      return positive[n] + negative[-n] 
    else: 
     return None 

print posneg([-1, 1, -4, 5]) 
print posneg([6, 44, 1, -7, -6, 19]) 

Funciona bien y es mucho más rápido que mi primer acercamiento.Gracias a Alon por el enlace de wikipedia y a ivazquez | laptop en #python irc channel por una buena pista que me condujo a la solución.

Creo que se puede optimizar aún más: quiero una manera de dejar de calcular la parte costosa una vez que se encuentre la solución. Seguire intentando.

Answer 5

Esto se puede resolver utilizando la programación entera. Puede definir una variable binaria s_i para cada uno de los elementos de su lista x_i y minimizar \ sum_i s_i, limitada por la restricción de que \ sum_i (x_i * s_i) es igual a la suma original de su lista.

Aquí es una implementación utilizando el paquete lpSolve en I:

library(lpSolve) 
get.subset <- function(lst) { 
    res <- lp("min", rep(1, length(lst)), matrix(lst, nrow=1), "=", sum(lst), 
      binary.vec=seq_along(lst)) 
    lst[res$solution > 0.999] 
} 

Ahora, podemos probar con algunos ejemplos:

get.subset(c(1, -1, -4, 5)) 
# [1] 1 
get.subset(c(6, 44, 1, -7, -6, 19)) 
# [1] 44 -6 19 
get.subset(c(1, 2, 3, 4)) 
# [1] 1 2 3 4