排列不重複

Question

我想知道，什麼是解決這個問題的最好辦法：

給定的x，y和y整數：A1，A2，A3 ..唉找到 A1 A2±所有組合±...±ay = x，y < 20.

我最近的做法是找到存儲在表T中的所有1和0的排列，然後根據數字T [i]是1還是0，添加或從總和中減去ai。問題是有n！ n元素陣列的排列。因此，對於20個元素的陣列，我必須檢查20個！其中大部分重複的可能性。你能否建議我解決我的問題的任何可能的方法？

Answer 1

只有2^20（超過一百萬）長度爲20的二元向量而不是不可行的20 !.使用應該能夠在少於一秒內蠻力，特別是如果您使用Gray Code，這將允許您在一個步驟中從一個候選人總和傳遞到另一個候選人總數（例如，從a + b - c -d到a + b - c + d只需添加2*d。

如果y得到更大@MikeWise的優秀分支界限的想法是很好的。生成開始的0根節點的一棵樹。給它的-a1和+a1孩子。然後4孫子通過加減a2等等。如果你從目標x得到的剩餘ai的總和超過 - 你可以修剪那個分支。在最壞的情況下，這可能會稍微差一些比基於格雷碼的蠻力（因爲你需要在每個節點上做更多的處理），但在最好的情況下，你可能會刪除大多數可能性。

關於編輯：這是一些Python代碼。首先我定義它，給出一個整數n發電機，先後返回其位的位置需要翻轉到步格雷碼：

def grayBit(n): 
    code = [0]*n 
    odd = True 
    done = False 
    while not done: 
     if odd: 
      code[0] = 1 - code[0] #flip bit 
      odd = False 
      yield 0 
     else: 
      i = code.index(1) 
      if i == n-1: 
       done = True 
      else: 
       code[i+1] = 1 - code[i+1] 
       odd = True 
       yield i+1 

（它使用一種算法，我多年前學到的優秀圖書「建設性組合「由斯坦頓和懷特）。

然後 - 我用它返回所有的解決方案（作爲輸入列表的數字與負號插入需要）。關鍵的一點是，我可以採取的當前比特 - 翻轉和添加或減去兩倍的相應數量：

def signedSums(nums, target): 
    n = len(nums) 
    patterns = [] 
    total = sum(nums) 
    pattern = [1]*n 
    if target == total: patterns.append([x*y for x,y in zip(nums,pattern)]) 
    deltas = [2*i for i in nums] 
    for i in grayBit(n): 
     if pattern[i] == 1: 
      total -= deltas[i] 
     else: 
      total += deltas[i] 
     pattern[i] = -1 * pattern[i] 
     if target == total: patterns.append([x*y for x,y in zip(nums,pattern)]) 
    return patterns 

典型輸出：

>>> signedSums([1,2,3,4,5,9],6) 
[[1, -2, -3, -4, 5, 9], [1, 2, 3, -4, -5, 9], [-1, 2, -3, 4, -5, 9], [1, 2, 3, 4, 5, -9]] 

只需要大約一秒鐘來評價：

>>> len(signedSums([i for i in range(1,21)],100)) 
2865 

因此有2865點的方式在範圍1,2-添加或減去的整數，...，20來獲得的100

淨總和

我認爲a1可以增加或減少（而不是剛剛添加，這是你的問題意味着如果字面意思）。請注意，如果您確實想要堅持a1出現正面，那麼您可以從x中減去它並將上述算法應用於列表的其餘部分和調整後的目標。

最後，這是不是太難看，如果你有一組權{2*a1, 2*a2, 2*a3, .... 2*ay}，並與x + a1 + a2 + ... + ay目標總和進而解決subset sub problem選擇的子集將正好對應到陽性體徵發生在溶液中的子集到原來的問題。因此，你的問題很容易歸結爲子集和問題，因此它是NP完全的，以確定它是否有任何解決方案（並且NP難以列出它們全部）。

Answer 2

我們具備的條件：

a1 ± a2 ± ... ± ay = x, y<20 [1] 

首先，我會概括的條件[1]，允許所有的 'A'，包括 'A1' 爲±：

±a1 ± a2 ± ... ± ay = x [2] 

如果我們有解決方案[2]中，我們可以很容易地得到[1]

爲了解決[2]我們可以用下面的辦法解決：

combinations list x 
    | x == 0 && null list = [[]] 
    | null list = [] 
    | otherwise = plusCombinations ++ minusCombinations where 
    a = head list 
    rest = tail list 
    plusCombinations = map (\c -> a:c) $ combinations rest (x-a) 
    minusCombinations = map (\c -> -a:c) $ combinations rest (x+a) 

說明：如果

1. 第一條件檢查X達到零和使用的所有號碼從名單。這意味着找到解決方案並返回單個解決方案：[[]]

2. 第二個條件檢查列表是否爲空，並且只要x不爲0，這意味着無法找到解決方案，返回空解決方案：[]

3. 第三分支意味着我們可以兩種選擇：使用AI與 '+' 或 ' - '，因此我們拼接正負組合

輸出示例：

*Main> combinations [1,2,3,4] 2 
[[1,2,3,-4],[-1,2,-3,4]] 
*Main> combinations [1,2,3,4] 3 
[] 
*Main> combinations [1,2,3,4] 4 
[[1,2,-3,4],[-1,-2,3,4]]