生成所有可能的組合效率低下

代碼，以生成數字列表的所有可能的組合，並與特定的總和取組合：生成所有可能的組合效率低下

combos = [] 

for each in combinations_with_replacement(list, number): 
    if sum(list(map(int, each))) == particular_number: 
     combos.append(list(map(int, each)))

的代碼工作完全正常。但問題是，如果在功能combinations_with_replacement數的說法是超過8則採取了大量的時間。有沒有一種優化的方式可以取代我的邏輯？

來源

2017-06-07 vikky 2405

好一兩件事你可以做'名單（圖（INT，每個））'一次，並將其分配給一個變量，而不是作爲if語句的一部分，它裏面 –

請提供一個完整的小例子。謝謝 – nCessity

是的，有很多更有效的方法來做到這一點。也許先從紙上解決問題開始（用一個小號碼），然後看看你遵循什麼算法。我已將此視爲面試問題，因此您可能也能在網上找到解決方案。 – smarx

首先，退出重複工作。

在進入循環之前將列表元素轉換爲整數。
該組合已經在一個元組中;你真的需要將它轉換爲combos的列表嗎？
代替生成所有組合適用於各種列表的長度，請嘗試使用遞歸的解決方案，您可以用查找「總和爲目標」的搜索。這將大大減少嘗試的列表數量。

遞歸解決方案的基本思路是：

# Given: remaining target sum and list of numbers (lon) to use 
if target = 0: 
    return [] 
if target < 0 or len(lon) == 0: 
    return None 

if target >= lon[0]: 
    # add one of the first number; recur 
    result = sum_to_target(target - lon[0], lon) 
    return result + [lon[0]] if result else None 

# Done with this number; try the rest of the list 
result = sum_to_target(target, lon[1:]) 
return result if result else None

嘗試每一步既沒有列表的第一個號碼。如果您超出目標或用完數字，則會失敗。如果您完全按下目標，則會成功：在抓取備用調用堆棧時構建有效的一組數字。

請注意，我已經離開了連接所有的解決方案作爲練習你......以及一些調試和邊界的細節問題。

來源

2017-06-07 23:36:12 Prune

生成所有可能的組合效率低下

回答

相關問題