从列表中移除数字而不改变总和

Question

我有一串数字（比如说：[-1, 1, -4, 5]），我需要从这个列表中去掉一些数字，但总和不能变。我想去掉绝对值最大的数字，确保总和不变。在这个例子中，去掉 [-1, -4, 5] 后，剩下的就是 [1]，这样总和就没变。

我写了一个简单的方法，就是找出所有可能的组合，看看哪些组合能去掉数字而不改变总和，最后找出去掉的绝对值最大的组合。但是这样做会很慢，因为实际的列表会比这个大得多。

这是我用来找组合的代码：

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

它正确地输出了 (-1, -4, 5)。不过我在寻找一种更聪明、更高效的解决方案，而不是遍历所有可能的组合。

有没有什么好主意呢？

Answer 1

你的需求没有说明这个函数是否可以改变列表的顺序。这里有一个可能的做法：

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

这个方法会先把列表排序（大的项目会排在最后，小的项目会排在最前），然后计算总和，并从列表中移除一个项目。接着，它会继续移除项目，直到新的总和等于原来的总和。如果你想保持顺序，可以写一个包装函数：

from copy import copy

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

不过，如果你真的想保持顺序，最好用 collections.deque 来重写这个代码。如果你能保证列表中的元素是唯一的，使用 set 会让你获得很大的性能提升。

我们可能还可以写一个更好的版本，每次遍历列表找到与当前总和最接近的两个数字，然后移除其中更接近的那个，但这样可能会导致性能变成 O(N^2)。我认为这个代码的性能是 O(N*log(N))，因为它只需要对列表进行排序（希望 Python 的列表排序不是 O(N^2)），然后再计算总和。

Answer 2

#!/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])

这个方法很好用，而且比我最开始的方法快多了。感谢Alon提供的维基百科链接，还有在#python的irc频道上给我提示的ivazquez|laptop，让我找到了这个解决方案。

我觉得这个方法还可以进一步优化——我想找到一种方法，一旦找到了解决方案，就停止计算那些耗时的部分。我会继续尝试的。

Answer 3

如果你把这个问题重新定义为寻找一个子集，使得这个子集的总和等于整个集合的总和，你会发现这其实是一个 NP-困难的问题，(子集和问题)。

所以，这个问题没有简单的解决办法，也就是说，没有一种能在合理时间内解决这个问题的方法。