Partition Problem

[Arne Leithe]

"Terry Reedy" <tjreedy at home.com> wrote in
news:fSI47.12086$p7.3693169 at news1.rdc2.pa.home.com: 

> [...]
> As for speed, P(50,6) takes 100 seconds on my machine (5427 partitions)
> while p6(50) and even p6(70) (26207 partitions) take less that a second
> to start printing.  P(70,6) would probably take hours to do the same.
> Computing exactly what you want with nothing wasted is always best.


I disagree :-) What's best in the majority of cases is an algorithm that's 
readable, maintainable, extensible etc. If speed isn't an issue (and nobody 
said it would be an issue in this case), there would be no reason 
whatsoever to optimise it for speed at the cost of the criterias mentioned 
above. In fact, he stated very well what he wanted - the sets of six 
numbers to sum up to 17 (and 20).

Quite often, though, a more general solution is required. In an algorithm 
like the one discussed here, we probably want to be able to change:

a) The "sum"
b) How many numbers to sum up
c) The minimum number in b) (including 0)

This all depends on the problem domain, though. Depending on the variations 
from the original problem, speed and memory might become issues, of course. 
What is important to avoid in any case, though, is repeating code where the 
number of repetitions depend on one of the criterias (as b above). I pity 
such code, it's almost as it's alive and begs to be put it out of its 
misery.

Anyway, here is a new version of the algorithm I posted before, this time 
speed is considered and you can specify criterium b in the function. (You 
actually specify the maxiumum of slots in the solution - if zeros can be 
part of the solution the rest can be filled with zeros.) 

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


> To solve this problem for any k using this approach, we could write a
> program that will write and compile the python code for a particular
> value of k (using x1 to xk instead of a to whatever).


But the said approach is very, very unmaintainable, even though it might be 
"exactly what he wants" in this case.


Arne Leithe