我正在尝试找到一种代码/算法来获取分割线或线段的所有可能排列。假设你有一条 5 英寸的线，你可以将它分成 5 block ，每 block 1 英寸，或者 2 x 2 英寸的段 + 1 段 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]
关于线分割排列的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43394451/