线细分排列的算法

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]