Algorithm for permutations of line subdivision

Question

I'm trying to find a code/algorithm to get all possible permutations of subdividing a line or a segment. Here goes, supposed you have a 5 inches line, you could divide it in 5 chunks of 1 inche each, or 2 x 2 inches segments + 1 segment of 1 inche...etc...

Is there an algorithm for finding all possible permutations of subdivision for a given segment?

Any help on this would be apreciated.

Thanks

Answer 1

You can do this by recursively choosing the length of the next segment.

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)

It wasn't clear if order was important, so this code supports both methods.

It prints out:

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]