python - 使用给定的所有数字，找出加法和减法可以组成的数字

Question

我分析了我的应用程序，它 90% 的时间都花在 plus_minus_variations 上。

该函数找到使用加法和减法在给定数字列表的情况下生成各种数字的方法。

例如:
输入

1, 2

输出

1+2=3
1-2=-1
-1+2=1
-1-2=-3

这是我当前的代码。我认为它在速度方面可以改进很多。

def plus_minus_variations(nums):
    result = dict()
    for i, ops in zip(xrange(2 ** len(nums)), \
            itertools.product([-1, 1], repeat=len(nums))):
        total = sum(map(operator.mul, ops, nums))
        result[total] = ops
    return result

我主要是在寻找一种不同的算法来解决这个问题。我现在的那个似乎效率很低。但是，如果您对代码本身有优化建议，我也很乐意听取。

附加:

• 如果结果缺少一些答案(或有一些无关的答案)，只要它完成得更快，那也没关系。
• 如果有多种获取号码的方法，任何一种都可以。
• 对于我使用的列表大小，99.9% 的方法会产生重复的数字。
• 如果结果与生成数字的方式不同也没关系，如果它完成得更快的话。

Answer 1

如果可以不获取数字生成的痕迹，则没有理由每次都重新计算数字组合的总和。您可以存储中间结果:

def combine(l,r):
    res = set()
    for x in l:
        for y in r:
            res.add( x+y )
            res.add( x-y )
            res.add( -x+y )
            res.add( -x-y )
    return list(res)

def pmv(nums):
    if len(nums) > 1:
        l = pmv( nums[:len(nums)/2] )
        r = pmv( nums[len(nums)/2:] )
        return combine( l, r )
    return nums

编辑:如果数字生成方式很重要，您可以使用此变体:

def combine(l,r):
    res = dict()
    for x,q in l.iteritems():
        for y,w in r.iteritems():
            if not res.has_key(x+y):
                res[x+y] = w+q
                res[-x-y] = [-i for i in res[x+y]]
            if not res.has_key(x-y):
                res[x-y] = w+[-i for i in q]
                res[-x+y] = [-i for i in res[x-y]]
    return res

def pmv(nums):
    if len(nums) > 1:
        l = pmv( nums[:len(nums)/2] )
        r = pmv( nums[len(nums)/2:] )
        return combine( l, r )
    return {nums[0]:[1]}

我的测试表明它仍然比其他解决方案更快。