受限整數組合的組合

-1

如何生成allowed_ints的組合列表，總和爲goal？受限整數組合的組合

例子：

allowed_ints=[1,2], goal=4 
combinations = [[1,1,1,1],[1,1,2],[2,1,1],[2,2],[1,2,1]] 

allowed_ints=[5, 6], goal=13 
combinations = []

我到目前爲止已經取得了哪些不工作。

def combinations(allowed_ints, goal): 
    if goal > 0: 
     for i in allowed_ints: 
      for p in combinations(allowed_ints, goal-i): 
       yield [i] + p 
    else: 
     yield [] 

print list(combinations([1, 2],3)) 
[[1, 1, 1], [1, 1, 2], [1, 2], [2, 1], [2, 2]] # not what I want

來源

2016-08-19 Ghilas BELHADJ

檢查您是否超過「目標」的閾值。 –

組合完成後（）？ –

你可以，但爲什麼推遲任務... –

使用功能你試試這個：

def combinations(allowed_ints, goal): 
    if goal > 0: 
     for i in allowed_ints: 
      for p in combinations(allowed_ints, goal-i): 
       if sum([i] + p) == goal: 
        yield [i] + p 
    else: 
     yield [] 

print list(combinations([1, 2],3))

輸出：

[[1, 1, 1], [1, 2], [2, 1]]

來源

2016-08-19 16:47:41

-1

您應該包括3個條件像

目標== 0，那麼遞歸工作

目標< 0，那麼遞歸失敗

目標> = 0和列表元素結束然後遞歸失敗

順便說一句，你可以做到這一切使用遞歸。無需循環，遞歸也可以做循環

來源

2016-08-19 16:23:01 Tahseen

我沒有誰標記我的答案是關閉的。我已經在Scala中編寫了硬幣組合程序，它發現了獨特的組合。實際上上面的程序給出了重複的響應，如1,2和2,1一樣 – Tahseen

我知道你已經選擇了一個答案，但我想提供與您的代碼不相似的替代方案。如果你想使用遞歸，我會建議這樣的：

def combinations(allowed_ints, list, goal): 
    # base case: you're done 
    if sum(list) == goal: 
     print list 
    # if overshoot, stop here 
    elif sum(list) > goal: 
     pass 
    else: 
     for i in allowed_ints: 
      new_list = list[:] 
      new_list.append(i) 
      combinations(allowed_ints, new_list, goal) 

combinations([1, 2],[],4)

它不比建議的答案更好，但使用不同的方法。

來源

2016-08-19 17:18:29 Noam

受限整數組合的組合

回答

相關問題