Partition Problem

[Arne Leithe]

"Donovan Hide" <donovanhide at bigfoot.com> wrote in
news:9itb14$2oi$1 at newsg1.svr.pol.co.uk: 

> [...]
> a=Partition(7,4)
> print a
> 
> [[4, 1, 1, 1], [3, 2, 1, 1],[2,2,2,1]]


How about this:

def Bags(res, start = 1): 
    	return [[i] + bag for i in range(start, res / 2 + 1) \
    	    	for bag in Bags(res - i, i)] + [[res]]

print filter(lambda e: len(e) == 4, Bags(7))

output: [[1, 1, 1, 4], [1, 1, 2, 3], [1, 2, 2, 2]]

You can of course extend the filter any way you like, or remove it.


Arne Leithe