线细分排列的算法

Question

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

线细分排列的算法

Algorithm for permutations of line subdivision

algorithm

permutation

partitioning

division

segment