[Tutor] Recursive Least Common Multiple

[Hans Nowak]

On 17 Jul 01, at 23:58, Timothy M. Brauch wrote:

> I would like to break up a number into its addition parts.  For example,
> with the number 7, I need a list returned like:
> [[1,6],[2,5],[3,4],[4,3],[5,2],[6,1],[1,1,5],[1,2,4],[1,3,3],[1,4,2],[1,5,
> 1],...[2,1,1,1,1,1],[1,1,1,1,1,1,1]]
> 
> Ideally, I can make this list smaller by sorting the individual lists and
> removing duplicates.  That is, I only need [1,6] not [6,1] and [2,5] not
> [5,2] and [1,1,1,1,1,2] not [2,1,1,1,1,1].  That part shouldn't be hard. 
> And speed is not a concern right now (it might be if I start using very
> large numbers, but I should be using mostly small numbers). I tried a
> small program that can break it into the groups of two numbers... I just
> can't seem to figure out how to get it to go on to 3 numbers, 4 numbers, 5
> numbers, and beyond.

Try this code:

def sums(n):
    if n == 1:
        return [[1]]
    lst = []
    for i in range(1, n):
        for r in sums(n-i) + [[n-i]]:
            t = [i] + r
            t.sort()
            if not t in lst: lst.append(t)
    return lst

# test it
for i in range(2, 9):
    print i, "=>", sums(i)

I didn't test it very thoroughly, but it seems to work. :)

HTH,

--Hans Nowak (zephyrfalcon@hvision.nl)
You call me a masterless man. You are wrong. I am my own master.
May a stockbroker marry your monogram!