algorithm - 线分割的置换算法

我正试图找到一个代码/算法来获得细分一条线或一段的所有可能的排列这里，假设你有一条5英寸的线，你可以把它分成5块，每块1英寸，或者2 x 2英寸的线段+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]