生成 x1 x2 ....xk = n, xi >= 0 的每個解的演算法是什么？我知道這是某種形式的回溯，但我不確定如何實作這一點。
uj5u.com熱心網友回復：
沒有遞回，用非零磁區從我的答案中快速修改，實作stars and bars原理
from itertools import combinations
#print(parts(7,4))
def partswithzeros(n,r):
result = []
for comb in combinations(range(n r-1), r-1):
zpart = [comb[0]] [comb[i]-comb[i-1]-1 for i in range(1,r-1)] [n r-2 - comb[-1]]
result.append(zpart)
return(result)
print(partswithzeros(5,3))
>>>[[0, 0, 5], [0, 1, 4], [0, 2, 3], [0, 3, 2], [0, 4, 1], [0, 5, 0], [1, 0, 4],
[1, 1, 3], [1, 2, 2], [1, 3, 1], [1, 4, 0], [2, 0, 3], [2, 1, 2], [2, 2, 1],
[2, 3, 0], [3, 0, 2], [3, 1, 1], [3, 2, 0], [4, 0, 1], [4, 1, 0], [5, 0, 0]]
uj5u.com熱心網友回復：
簡單的遞回將在這里作業。解的第一個元素可以取從 0 到n的任何值x i。要找到第二個和后續值，請找到 ( n - x i , k -1) 的可能磁區。當k =1 時遞回停止，在這種情況下，最終元素必須等于n的剩余值。
我希望這是有道理的。也許以下 Python 代碼會有所幫助：
def get_partitions(n, k, p=[]):
# End point. If k=1, then the last element must equal n
# p[] starts as an empty list; we will append values to it
# at each recursive step
if k <= 1:
if k == 1 and n >= 0:
yield(p [n])
return
# If k is zero, then there is no solution
yield None
# Recursively loop over every possible value for the current element
for i in range(0,n 1):
yield from get_partitions(n-i, k-1, p [i])
>>> for p in get_partitions(4,3):
... print(p)
...
[0, 0, 4]
[0, 1, 3]
[0, 2, 2]
[0, 3, 1]
[0, 4, 0]
[1, 0, 3]
[1, 1, 2]
[1, 2, 1]
[1, 3, 0]
[2, 0, 2]
[2, 1, 1]
[2, 2, 0]
[3, 0, 1]
[3, 1, 0]
[4, 0, 0]
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/507820.html