Nummern aus einer Liste entfernen, ohne Gesamtsumme zu ändern

Question

Ich habe eine Liste von Nummern (Beispiel: [-1, 1, -4, 5]) und ich muss Nummern aus der Liste entfernen, ohne die Gesamtsumme der Liste zu ändern. Ich möchte die Zahlen mit dem größten absoluten Wert, der möglich ist, entfernen, ohne die Summe zu ändern, in dem Beispiel wird das Entfernen [-1, -4, 5][1] verlassen, so ändert sich die Summe nicht.

Ich schrieb den naiven Ansatz, der alle möglichen Kombinationen findet, die die Summe nicht ändern und sehen, welche den größten absoluten Wert entfernt. Aber das ist wirklich langsam, da die tatsächliche Liste viel größer sein wird.

Hier ist meine Kombinationen Code:

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]) 

Es corectly (-1, -4, 5) druckt. Ich suche jedoch nach einer cleveren, effizienteren Lösung, als alle möglichen Artikelkombinationen zu durchlaufen.

Irgendwelche Ideen?

Answer 1

wenn Sie das Problem wie die Suche nach einer Teilmenge, deren Summe gleich den Wert des vollständigen Satzes neu zu definieren, werden Sie feststellen, dass dies ein NP-hartes Problem, (subset sum)

so gibt es keine Polynom Komplexität Lösung für dieses Problem .

Answer 2

Ich programmiere nicht in Python und entschuldige mich dafür, dass ich keinen Code anbiete. Aber ich denke, ich mit dem Algorithmus helfen kann:

1. Finden Sie die Summe
2. Zahlen hinzufügen mit dem niedrigsten Wert, bis Sie auf die gleiche Summe erhalten
3. Alles andere
gelöscht werden können

I hoffe das hilft

Answer 3

Ihre Anforderungen sagen nicht, ob die Funktion die Reihenfolge der Liste ändern darf oder nicht. Hier ist eine Möglichkeit:

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 

Dies sortiert die Liste (große Gegenstände am Ende sein werden, wird kleinere am Anfang sein) und berechnet die Summe und entfernt ein Element aus der Liste. Es fährt fort, Elemente zu entfernen, bis die neue Summe der ursprünglichen Summe entspricht.

from copy import copy 

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

Obwohl Sie es wahrscheinlich mit collections.deque umschreiben sollte, wenn Sie wirklich, um bewahren wollen: Eine alternative Version, die Reihenfolge bewahrt kann als Wrapper geschrieben werden. Wenn Sie die Eindeutigkeit in Ihrer Liste garantieren können, können Sie einen großen Gewinn erzielen, indem Sie stattdessen eine set verwenden.

Wir könnten wahrscheinlich eine bessere Version schreiben, die die Liste durchläuft, um jedes Mal die zwei Zahlen zu finden, die der laufenden Summe am nächsten sind, und die nähere der beiden entfernen, aber dann würden wir wahrscheinlich mit O (N^2) enden. Performance. Ich glaube, dass die Leistung dieses Codes O (N * log (N)) sein wird, da es nur die Liste sortieren muss (ich hoffe, dass Pythons Listensortierung nicht O (N^2) ist) und dann die Summe erhält.

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]) 

Es funktioniert gut und ist viel schneller als mein erster Ansatz.Danke an Alon für den wikipedia link und den ivazquez | laptop auf #python irc channel für einen guten Hinweis, der mich in die Lösung geführt hat.

Ich denke, es kann weiter optimiert werden - ich möchte einen Weg, um die teure Teil zu berechnen, sobald die Lösung gefunden wurde. Ich werde es weiter versuchen.

Answer 5

Dies kann mit Integer-Programmierung gelöst werden. Sie können eine Binärvariable s_i für jedes Ihrer Listenelemente x_i und minimize \ sum_i s_i definieren, begrenzt durch die Einschränkung, dass \ sum_i (x_i * s_i) gleich der ursprünglichen Summe Ihrer Liste ist.

Hier ist eine Implementierung mit dem lpSolve Paket in R:

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] 
} 

Nun können wir es mit einigen Beispielen testen:

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