整數的所有排列對應於特定總和

Question

我想從整數列表[3,5,7,9]中產生所有排列，其導致特定總和值15。我實現了這一點，沒關係。

def add_next(seq, count, m): 
    s = sum(seq) 
    if s == m: 
     count += 1 
     print(seq) 
    elif s < m: 
     for i in [3,5,7,9]: 
      add_next(seq + [i], count, m) 
    else: 
     return count 

add_next([], 0, 15) 

輸出：

[3, 3, 3, 3, 3] 
[3, 3, 9] 
[3, 5, 7] 
[3, 7, 5] 
[3, 9, 3] 
[5, 3, 7] 
[5, 5, 5] 
[5, 7, 3] 
[7, 3, 5] 
[7, 5, 3] 
[9, 3, 3] 

的問題是如何重新寫這個函數返回可能的排列只是數作爲函數的結果？由於對於巨大的列表和大數值，生成所有字符串輸出是不合理的。我不完全理解如何傳遞遞歸函數內外的值。

我想：

def add_next2(seq, count, m): 
    s = sum(seq) 
    if s == m: 
     count += 1 
     print(seq) 
    elif s < m: 
     for i in [3,5,7,9]: 
      count = add_next2(seq + [i], count, m) 
    else: 
     return count 

add_next([], 0, 15) 

但retuns錯誤TypeError: unsupported operand type(s) for +=: 'NoneType' and 'int'。所以count是None。爲什麼？

另一個選擇是如何重寫這個函數來將其轉換爲生成器並且一個接一個地生成輸出串？

Answer 1

如果你只是算成功的遞歸結果，你並不需要「數'作爲參數。您可以將成功的結果作爲1返回，並且不成功爲0，讓它們累積。

EDIT 2一點更簡潔但仍然可讀

def add_next(seq, m): 
    s = sum(seq) 
    count = 1 if s == m else 0 
    if s < m: 
     for i in [f for f in [3,5,7,9] if s + f <= m]: 
      count += add_next(seq + [i], m) 
    return count 

print(add_next([], 15)) 

編輯您還可以過濾[3,5,7,9]列表，這樣你對我在僅環與交易有可能成功的元素。

for i in [f for f in [3,5,7,9] if s + f <= m]: 

Answer 2

您的遞歸函數不會返回s <= m的值。對於這些情況，請返回某些東西，否則返回None。

最有可能要在所有情況下返回count：

def add_next2(seq, count, m): 
    s = sum(seq) 
    if s == m: 
     count += 1 
    elif s < m: 
     for i in [3,5,7,9]: 
      count = add_next2(seq + [i], count, m) 
    return count 

這則作品：

>>> def add_next2(seq, count, m): 
...  s = sum(seq) 
...  if s == m: 
...   count += 1 
...  elif s < m: 
...   for i in [3,5,7,9]: 
...    count = add_next2(seq + [i], count, m) 
...  return count 
... 
>>> add_next2([], 0, 15) 
11