線細分排列的算法

Question

我試圖找到一個代碼/算法來獲得細分線或細分的所有可能的排列組合。在這裏，假設你有一個5英寸的線，你可以把它分成5個塊，每塊1英寸，或者2×2英寸的段+ 1段的1英寸等等......

有沒有算法爲特定的細分找到所有可能的細分排列？

對此的任何幫助都會有所幫助。

感謝

Answer 1

您可以通過遞歸選擇下一段的長度做到這一點。

def find_partitions(length_remaining,only_decreasing_lengths=True,A=None): 
    longest = length_remaining 
    if A is None: 
     A = [] 
    elif only_decreasing_lengths: 
     longest = min(longest,A[-1]) 
    if longest==0: 
     print A 
    for x in range(1,longest+1): 
     find_partitions(length_remaining-x,only_decreasing_lengths,A+[x]) 

print 'Decreasing' 
find_partitions(5) 
print 'Any order' 
find_partitions(5,False) 

目前還不清楚訂單是否重要，所以此代碼支持這兩種方法。

它打印出：

Decreasing 
[1, 1, 1, 1, 1] 
[2, 1, 1, 1] 
[2, 2, 1] 
[3, 1, 1] 
[3, 2] 
[4, 1] 
[5] 
Any order 
[1, 1, 1, 1, 1] 
[1, 1, 1, 2] 
[1, 1, 2, 1] 
[1, 1, 3] 
[1, 2, 1, 1] 
[1, 2, 2] 
[1, 3, 1] 
[1, 4] 
[2, 1, 1, 1] 
[2, 1, 2] 
[2, 2, 1] 
[2, 3] 
[3, 1, 1] 
[3, 2] 
[4, 1] 
[5]