正如標題所說：要寫的函式有2個引數，第一個是數字，第二個是數字串列：
例如：(7, [5,3,4,7]) 要撰寫的 Python 函式應該回傳一個數字串列，當添加這些數字時會導致“7”，例如 [3,4] 或 [4,3] 或 [ 7]
我寫了一個實際作業的 Python 函式（見下面的 bestSum()），但它只回傳 1 個作業組合，我希望有人可以幫助編輯它，以便它回傳所有可能的“好”組合。然后我可以選擇最短的一個。
遞回 Python 函式是使用二叉樹通過從串列中減去一個數字到主數字（減去相同的數字就可以）來向下走。如果最后一個節點中有 0 則它是贏家，但如果結果為負，則它是一個不可能的組合，應該丟棄。
因此，而不是僅僅回傳，比如說 [4,3]，它會回傳：([3,4], [4,3], [7]) 或者至少幫助我改變回圈，這樣它就不會在之后停止它找到第一個作業組合。
def bestSum(nb, intlist, res=[[], []]):
if (nb == 0):
res[0] = True
return res
if (nb < 0):
res[0] = False
return res
for i in intlist:
remainder = nb - i
res = bestSum(remainder, intlist, res)
if (res[0] == True):
res[1].append(i)
res[0] = True
return res
res[0] = False
return res
現在這兩行代碼
res = bestSum(7, [5,3,4,7])
print("Shortest Result list is = ", res[1])
將回傳：
最短的結果串列是 = [4, 3]
（這不是最短的，應該是[7]）
注意：這與硬幣找零問題不同，因為硬幣問題也包括美分并且總是有解決方案，而在這里我們沒有。所以這里并不總是有解決方案，例如在 (7, [4,5]) 的情況下，沒有 4 和 5 的組合可以添加到 7。
謝謝
uj5u.com熱心網友回復：
的根本問題是：
我有一個遞回演算法。當我進行一次或多次遞回呼叫時，我想從這些遞回呼叫中收集結果，并使用它們來生成此級別遞回的結果。（最簡單的情況：我想要一個所有遞回結果的串列。）我怎樣才能簡單地做到這一點？
當我們不依賴任何副作用或可變資料結構時，更容易推理遞回演算法。修改串列——尤其是當它們是用作快取的默認引數時——很快就變得令人頭疼。即使我們從遞回呼叫（比如 a tuple）中得到一些不可變的資料并想要組合這些結果，這通常也很尷尬。（例如，可能很難記住某些葉結果應該是()或 單例元組，而不是None或特定的元素值。）
在解決這個辦法，我建議，是使用遞回發生器來代替。然而，我想展示幾種方法，以解釋遞回演算法的一些通用技術。
讓我們首先考慮以深度優先順序列出樹中所有節點的簡單示例：
def all_nodes_at(root):
# If this is a leaf node, then `root.children` is empty;
# so the loop will simply not run and nothing is yielded.
for child in root.children:
yield from all_nodes_at(child)
yield root # include the current node, after all nodes underneath.
# To see the results, we need to iterate over the generator in some way:
tree_nodes = list(all_nodes_at(tree_root))
將其與使用元組的方法進行比較：
def all_nodes_at(root):
result = ()
for child in root.children:
result = result all_nodes_at(child)
return result (root,)
tree_nodes = all_nodes_at(tree_root)
對我來說似乎更丑。使用串列快取：
def all_nodes_at(root, cache=[]):
for child in root.children:
cache.extend(all_nodes_at(child))
cache.append(root)
return cache
tree_nodes = all_nodes_at(tree_root)
錢幣。我們不僅被迫使用return一個我們實際上沒有在遞回中使用的值（以便我們在頂層獲得結果），而且如果我們想要多次使用它，它就會中斷。“哦，沒關系，我們先清空快取就好了。” 真的嗎？您想記錄用戶all_nodes_at.__defaults__[0].clear()在呼叫函式之前需要做的事情嗎？當然最好不要默認引數。如果它不是默認引數并且用戶提供了初始快取，那就更好了：
def dump_all_nodes_at(root, cache):
for child in root.children:
cache.extend(all_nodes_at(child))
cache.append(root)
tree_nodes = []
dump_all_nodes_at(tree_root, tree_nodes)
至少這個是可以復用的，我們不用和回傳值玩傻游戲（事實上，我們根本沒必要return）。但它現在是一個非常尷尬的界面。
你會明白為什么我通常更喜歡遞回生成器。
讓我們將該技術應用于查找具有給定總和的所有子集的問題。但首先，我們需要清楚地考慮遞回演算法。我們實際上并不想在演算法的給定步驟中嘗試每個元素。為什么？因為如果我們只嘗試第一個元素，那么其他元素將在遞回中的后續步驟中處理。當然，這意味著我們無法獲得給定結果集的所有可能排序；但我們可以稍后修復它，例如，itertools.permutations如果它真的很重要。（此外，我很確定您的方法不會阻止多次使用相同的元素。）
簡單的定義如下：具有給定總和的子集要么包含第一個元素，要么不包含。我們的子集包括
- elements from the previous levels of the recursion that we decided to include;
- possibly the current element;
- elements from a recursive call on the remaining elements.
What we'll do is prepend the current element to results from the recursive call where appropriate (i.e., the one where we recursively called with a smaller target sum). The other elements will get automatically prepended as we bubble back through the recursion.
Thus:
def subsets_with_sum(values, target):
if target < 0:
# There are no solutions, so bail out.
return
if not values:
# Nesting the check like this allows for zeros in `values`.
if target == 0:
# We have reached the trivial solution.
yield ()
# No current element, therefore no more solutions.
return
# Otherwise, we recurse twice, yielding sub-results.
# First, some useful renaming
this_value, *other_values = values
for subset in subsets_with_sum(other_values, target - this_value):
yield (this_value,) subset # prepend and yield it back
# `yield from` is sugar for iterating and yielding each result directly.
yield from subsets_with_sum(other_values, target)
Let's test it:
>>> list(subsets_with_sum([5,4,3,7], 7))
[(4, 3), (7,)]
>>> list(subsets_with_sum(range(10), 10))
[(0, 1, 2, 3, 4), (0, 1, 2, 7), (0, 1, 3, 6), (0, 1, 4, 5), (0, 1, 9), (0, 2, 3, 5), (0, 2, 8), (0, 3, 7), (0, 4, 6), (1, 2, 3, 4), (1, 2, 7), (1, 3, 6), (1, 4, 5), (1, 9), (2, 3, 5), (2, 8), (3, 7), (4, 6)]
uj5u.com熱心網友回復：
根據問題中的評論，我們可以intlist 多次選擇相同的元素以形成總結為給定 的組合target。
迭代解決
在這里，我們逐步遍歷 中的不同值intlist并構建一個新的組合，匯總到給定的總和，然后在其中添加新數字。
def bestSum(target, intlist):
# initialize the dp dict
dp = {} # dp[combinationSum] = combination
for num in intlist:
dp[num] = [num]
# max steps we would need to arrive at a valid combination(if it exists) would be
# the combination containing only the min element in the intlist
# e.g. for target = 20 and intlist = [2,7], if we don't find a valid combination within
# 10 steps(all 2's), no valid answer would exist
for step in range(target//min(intlist) 1):
for combinationSum, combination in dp.copy().items(): # avoid modifying the dict while itrating
for i in intlist:
newSum = combinationSum i
if newSum == target:
# since we are taking a step one at a time, the first sum being equal to target
# will guarantee a shortest combination
return combination [i]
if newSum > target:
# skip if newSum if over target(skip adding additional entries into dp to improve perf)
continue
if not dp.get(newSum):
# if the dp already has an non-zero length list in it = its length is going to be
# at least equal to new combination length or lower, so we don't need to overwrite it
dp[newSum] = combination [i]
target, intlist = 20, [5,3,4,7]
print(bestSum(target, intlist))
印刷
[5, 5, 5, 5]
為簡單起見，以下是我們dp在每個步驟中的內容intlist = [5,3,4,7]和目標20-
Step : 0 - dp: {3: [3], 4: [4], 5: [5], 7: [7]}
Step : 1 - dp: {3: [3], 4: [4], 5: [5], 6: [3, 3], 7: [7], 8: [5, 3], 9: [5, 4], 10: [5, 5], 11: [4, 7], 12: [5, 7], 14: [7, 7]}
Step : 2 - dp: {3: [3], 4: [4], 5: [5], 6: [3, 3], 7: [7], 8: [5, 3], 9: [5, 4], 10: [5, 5], 11: [4, 7], 12: [5, 7], 13: [5, 5, 3], 14: [7, 7], 15: [5, 5, 5], 16: [5, 4, 7], 17: [5, 5, 7], 18: [4, 7, 7], 19: [5, 7, 7]}
Step : 3 - dp: {3: [3], 4: [4], 5: [5], 6: [3, 3], 7: [7], 8: [5, 3], 9: [5, 4], 10: [5, 5], 11: [4, 7], 12: [5, 7], 13: [5, 5, 3], 14: [7, 7], 15: [5, 5, 5], 16: [5, 4, 7], 17: [5, 5, 7], 18: [4, 7, 7], 19: [5, 7, 7], 20: [5, 5, 5, 5]}
遞回解
如果您想堅持使用遞回方法，您可以對原始代碼進行小幅更改，使其回傳總和到所需目標的所有組合。
首先，我們不需要讓函式 return True/False，相反，我們可以None在沒有有效組合與目標值相加的情況下回傳。
我們想要收集總和為所需值的所有組合，因此我們應該做的不是在找到有效組合時回傳函式，而是將其保存在稍后可以訪問的地方。
combinations = []
def bestSum(target, intlist, res=[]):
if (target == 0):
# found a valid combination
combinations.append(res) # collect the current combinations - THIS is what you were looking for
return
if (target < 0):
return
for i in intlist:
remainder = target - i
bestSum(remainder, intlist, res [i])
target, intlist = 20, [5, 4, 3, 7]
bestSum(target, intlist)
print(combinations, len(combinations))
現在所有與目標相加的組合現在都被寫入組合，但這有一些問題..
上面的代碼列印 -
[[5, 5, 5, 5], [5, 5, 4, 3, 3], [5, 5, 3, 4, 3], [5, 5, 3, 3, 4], [5, 5, 3, 7], [5, 5, 7, 3], [5, 4, 5, 3, 3], [5, 4, 4, 4, 3], [5, 4, 4, 3, 4], [5, 4, 4, 7], [5, 4, 3, 5, 3], [5, 4, 3, 4, 4], [5, 4, 3, 3, 5], [5, 4, 7, 4], [5, 3, 5, 4, 3], [5, 3, 5, 3, 4], [5, 3, 5, 7], [5, 3, 4, 5, 3], [5, 3, 4, 4, 4], [5, 3, 4, 3, 5], [5, 3, 3, 5, 4], [5, 3, 3, 4, 5], [5, 3, 3, 3, 3, 3], [5, 3, 7, 5], [5, 7, 5, 3], [5, 7, 4, 4], [5, 7, 3, 5], [4, 5, 5, 3, 3], [4, 5, 4, 4, 3], [4, 5, 4, 3, 4], [4, 5, 4, 7], [4, 5, 3, 5, 3], [4, 5, 3, 4, 4], [4, 5, 3, 3, 5], [4, 5, 7, 4], [4, 4, 5, 4, 3], [4, 4, 5, 3, 4], [4, 4, 5, 7], [4, 4, 4, 5, 3], [4, 4, 4, 4, 4], [4, 4, 4, 3, 5], [4, 4, 3, 5, 4], [4, 4, 3, 4, 5], [4, 4, 3, 3, 3, 3], [4, 4, 7, 5], [4, 3, 5, 5, 3], [4, 3, 5, 4, 4], [4, 3, 5, 3, 5], [4, 3, 4, 5, 4], [4, 3, 4, 4, 5], [4, 3, 4, 3, 3, 3], [4, 3, 3, 5, 5], [4, 3, 3, 4, 3, 3], [4, 3, 3, 3, 4, 3], [4, 3, 3, 3, 3, 4], [4, 3, 3, 3, 7], [4, 3, 3, 7, 3], [4, 3, 7, 3, 3], [4, 7, 5, 4], [4, 7, 4, 5], [4, 7, 3, 3, 3], [3, 5, 5, 4, 3], [3, 5, 5, 3, 4], [3, 5, 5, 7], [3, 5, 4, 5, 3], [3, 5, 4, 4, 4], [3, 5, 4, 3, 5], [3, 5, 3, 5, 4], [3, 5, 3, 4, 5], [3, 5, 3, 3, 3, 3], [3, 5, 7, 5], [3, 4, 5, 5, 3], [3, 4, 5, 4, 4], [3, 4, 5, 3, 5], [3, 4, 4, 5, 4], [3, 4, 4, 4, 5], [3, 4, 4, 3, 3, 3], [3, 4, 3, 5, 5], [3, 4, 3, 4, 3, 3], [3, 4, 3, 3, 4, 3], [3, 4, 3, 3, 3, 4], [3, 4, 3, 3, 7], [3, 4, 3, 7, 3], [3, 4, 7, 3, 3], [3, 3, 5, 5, 4], [3, 3, 5, 4, 5], [3, 3, 5, 3, 3, 3], [3, 3, 4, 5, 5], [3, 3, 4, 4, 3, 3], [3, 3, 4, 3, 4, 3], [3, 3, 4, 3, 3, 4], [3, 3, 4, 3, 7], [3, 3, 4, 7, 3], [3, 3, 3, 5, 3, 3], [3, 3, 3, 4, 4, 3], [3, 3, 3, 4, 3, 4], [3, 3, 3, 4, 7], [3, 3, 3, 3, 5, 3], [3, 3, 3, 3, 4, 4], [3, 3, 3, 3, 3, 5], [3, 3, 3, 7, 4], [3, 3, 7, 4, 3], [3, 3, 7, 3, 4], [3, 3, 7, 7], [3, 7, 5, 5], [3, 7, 4, 3, 3], [3, 7, 3, 4, 3], [3, 7, 3, 3, 4], [3, 7, 3, 7], [3, 7, 7, 3], [7, 5, 5, 3], [7, 5, 4, 4], [7, 5, 3, 5], [7, 4, 5, 4], [7, 4, 4, 5], [7, 4, 3, 3, 3], [7, 3, 5, 5], [7, 3, 4, 3, 3], [7, 3, 3, 4, 3], [7, 3, 3, 3, 4], [7, 3, 3, 7], [7, 3, 7, 3], [7, 7, 3, 3]] 123
高達 123 種組合僅適用于20. 如果您查看組合串列，您會注意到combinations包含給定有效組合的所有排列會導致這種膨脹的大小。代碼還必須做額外的作業來匯出所有這些組合。
What can we do to avoid these duplicates?
Sorting comes to the rescue; if we ensure that each valid combination is always sorted then there cannot be a permutation of the same combination in final combinations. How can this be leveraged in the code?
combinations = []
def bestSum(target, intlist, combination=[]):
if (target == 0):
# found a valid combination
combinations.append(combination)
return
if (target < 0):
return
for i in intlist[::-1]:
# each combination will be in ascending order
# while i is in descending order here, so if last element in my
# combination is greater than i, we can break the loop to stop
# additional work, and make sure that all the combinations are unique
if combination and combination[-1] > i:
break
remainder = target - i
bestSum(remainder, intlist, combination [i])
target, intlist = 20, [5, 4, 3, 7]
bestSum(target, sorted(intlist)) # sort list of values
print(combinations, len(combinations))
this outputs
[[5, 5, 5, 5], [4, 4, 5, 7], [4, 4, 4, 4, 4], [3, 5, 5, 7], [3, 4, 4, 4, 5], [3, 3, 7, 7], [3, 3, 4, 5, 5], [3, 3, 3, 4, 7], [3, 3, 3, 3, 4, 4], [3, 3, 3, 3, 3, 5]] 10
Now, we don't have any permutations in our combinations! And we can easily get all the shortest/longest combinations as needed from the combinations.
But as pointed out by @karl in his answer, the interface for this looks quite bad, and we should actually use recursive generators to make the interface cleaner. Which would look something like this -
def bestSum(target, intlist, combination=[]):
if (target == 0):
# found a valid combination
yield combination
if (target < 0):
return
for i in intlist[::-1]:
if combination and combination[-1] > i:
break
remainder = target - i
yield from bestSum(remainder, intlist, combination [i])
target, intlist = 20, [5, 4, 3, 7]
intlist.sort()
targetCombinations = list(bestSum(target, intlist))
targetCombinations.sort(key=lambda x: len(x))
print("One of the shortest combination - ", targetCombinations[0])
Returning only one of the shortest path using recursion - this is not possible using just the return and use of a single recursion function since once we return a value, we won't be able to keep on searching through the remaining combinations. So a way to get around this would be to wrap your recursion function in another function and make that return the shortest combination you come across after going through all combinations or use a global variable (I would avoid going the global variable way) or pass a variable by reference to the original function.
def shortestCombinationSum(target, intlist, combination=[]):
shortest = None
def bestSum(target, intlist, combination):
nonlocal shortest
if (target == 0 and (not shortest or len(combination) < len(shortest))):
# found a valid combination which is shorter
shortest = combination
return
if (target < 0):
return
for i in intlist[::-1]:
if combination and combination[-1] > i:
break
remainder = target - i
bestSum(remainder, intlist, combination [i])
bestSum(target, intlist, combination)
return shortest
target, intlist = 20, [5, 4, 3, 7]
print(shortestCombinationSum(target, sorted(intlist)))
Although this makes the function look weird, the interface for the shortestCombinationSum is fairly clean. Another alternative could've been making shortest as a global variable and then keep updating it, we would not have to wrap the function in another function in that case, but we will have to clear the value of the global variable in case we are calling the function over and over again with different sets of inputs.
I would still recommend the iterative solution over the recursive solution above because given an intlist of size n, the tree you have in your diagram would be an n-ary tree, having n branches on each node starting from target at the top. The iterative solution would be similar to a level order traversal in the n-ary tree and would stop when it reaches the level where it finds the solution. While the recursive solution would be DFS over the tree and it would need to go through each and every combinations(pruning duplicate permutations) of the n-ary tree.
uj5u.com熱心網友回復：
這是一個簡單的：
import itertools as it
# create all possible route
def create_permutation(data):
final = []
for k in range(1, len(data) 1):
temp = list(it.permutations(data, k))
final.extend(temp)
return final
# find best sum in equal to num
def best_sum(subs, num, _min = True):
final = []
for i in range(len(subs)):
temp_sums = sum(subs[i])
if temp_sums == num:
final.append(subs[i])
if not final:
return None
# if only wants minimum then sort by length then return first
if _min:
return sorted(final, key = lambda x : len(x))[0]
return final
def main(data, num):
subs = create_permutation(data)
result = best_sum(subs, num, False)
print("Best === ", result)
data = [5, 3, 4, 7, 2]
num = 7
main(data, num)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/403067.html
標籤：
上一篇：序言中的歸并排序-無限遞回？