Python 为特定结果设置要加或减的数字序列

Question

在这个假设的场景中，我有一个 sequence 的已知数字，但长度是随机的，我需要将序列中的每个数字设置为 add 或减去以达到给定的输出并显示过程。

有没有不用重新发明轮子的方法，比如模块？

编辑：更多信息：

我有一个数字序列，例如：5 4 3 2 1，我需要将每个数字设置为加 (+) 或减 (-) 以获得诸如 7 之类的结果。在这种情况下，结果将是5+4-3+2-1。只要有可能的结果，它可以是任何数字的序列。如果有多个正确答案，只需其中一个即可。

编辑：

Let's assume that no step in the equation results in an answer larger than 1000.

Answer 1

最简单的方法是暴力破解所有可能的加号和减号组合，return 第一个总和正确的组合。您可以使用 itertools.product 来执行此操作。

import itertools

def find_correct_operators(seq, total):
    signs = [-1,1]
    for item_signs in itertools.product(*[signs]*len(seq)):
        seq_with_signs_applied = [item*sign for item, sign in zip(seq, item_signs)]
        sum(seq_with_signs_applied)
        if sum(seq_with_signs_applied) == total:
            return item_signs

a = [5,4,3,2,1]
b = 7
signs = find_correct_operators(a,b)
if signs is not None:
    print "{} = {}".format(" ".join("{}{}".format("-" if sign == -1 else "+", item) for sign, item in zip(signs, a)), b)
else:
    print "No solution found"

结果：

+5 -4 +3 +2 +1 = 7

这样做的缺点是它的运行时间为 O(2^N)，因此它非常不适合任何大于 20 项长度的数字序列。到那时，您正在迭代超过一百万种可能的组合。

编辑：如果你有一些限制 L 并且等式中没有任何中间步骤的计算结果可能永远大于 L 或小于 -L，那么你可以在中找到答案O(N*L) 时间，这对于较小的 L 值来说是一个相当大的改进。

seq = [5,4,-3,2,1]
goal = 7
limit = 1000
d = {0: []}
for item in seq:
    next_d ={}
    for intermediary_total, path in d.iteritems():
        for candidate in [-item, item]:
            next_total = intermediary_total + candidate
            if abs(next_total) <= limit:
                next_d[next_total] = path + [candidate]
    d = next_d

if goal in d:
    print d[goal]
else:
    print "no solution found"

结果：

[5, 4, -3, 2, -1]

Python 为特定结果设置要加或减的数字序列

Python set sequence of numbers to add or subtract for certain result

python

algorithm

math

sequence

iterable