我需要一種算法來生成所有可能的正數分區，然后我想到了一個算法（作為答案發布），但這是指數時間。該算法應返回所有可能的方式，以小于或等于其自身的正數之和表示一個數字。因此，例如對于數字5，結果將是：54 + 13 + 23 + 1 + 12 + 2 + 12 + 1 + 1 + 11 + 1 + 1 + 1 + 1所以我的問題是：有沒有更有效的算法呢？編輯：問題的標題是“一個數字的總和分解”，因為我真的不知道這叫什么。ShreevatsaR指出它們被稱為“分區”，因此我相應地編輯了問題標題。
3 回答
慕桂英546537
TA貢獻1848條經驗 獲得超10個贊
它稱為分區。[另請參閱Wikipedia：分區（數論）。]
分區的數量p（n）呈指數增長，因此生成所有分區的所有操作都必須花費指數時間。
也就是說，您可以做得比代碼更好。請參見David Eppstein在Python Algorithms and Data Structures中的此版本或其更新版本。
函數式編程
TA貢獻1807條經驗 獲得超9個贊
這是我在Python中的解決方案（指數時間）：
q = { 1: [[1]] }
def decompose(n):
try:
return q[n]
except:
pass
result = [[n]]
for i in range(1, n):
a = n-i
R = decompose(i)
for r in R:
if r[0] <= a:
result.append([a] + r)
q[n] = result
return result
>>> decompose(5)
[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]
添加回答
舉報
0/150
提交
取消