數的Python組序列增加或減少某些結果

Question

在這種假設的情況我的已知數字的序列，但隨機長度，我需要設置序列每個號碼添加或減以達到給定的輸出並顯示過程。

有沒有辦法做到這一點，而不重新發明輪子，如模塊？

編輯：更多信息：

我有像數字的序列：5 4 3 2 1和I需要設置每個號碼添加（+）或減（ - ），以獲得一個結果，例如7在這種情況下的結果是5 + 4-3 + 2-1。只要有可能的結果，它可以是任何數字的序列。如果有多個正確的答案，只有其中一個會做。

編輯：

讓我們假設，在方程結果沒有一步一個答案大於1000

Answer 1

最簡單的方法是隻蠻力加號和減號的所有可能的組合，並返回第一個具有正確總和的那個。您可以使用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）時運行，所以它是非常不適合比說，二十項長期較大的任意序列。到那時，你正在遍歷超過一百萬種可能的組合。

---

編輯：如果你有一些限制大號和公式中沒有中間步驟可能永遠評估爲小於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]