Partition Problem

[Terry Reedy]

"Arne Leithe" <arne at leithe.spammenot.no> wrote in message
news:Xns90E1CD0C46990arneleitheno at 148.122.208.67...
> "Terry Reedy" <tjreedy at home.com> wrote in
> news:0oR47.12485$p7.4220508 at news1.rdc2.pa.home.com:
>
> > So why do you object when I revise an algorith to make it feasible for
> > much larger n?
>
> Because you optimized a brute force-algorithm for speed, without first
> fixing the algorithm (first and foremost the ability to vary "k").

*My* original purpose was to illustrate how one can improve a brute-force
branching algorithm by pruning the tree (in this case, by improving the
loop upper bounds).  When I discovered how to make both upper and lower
bounds exact, so as to prune *all* unneeded branches, so much better the
lesson.  For *this purpose*, the original and my first revision are quite
good, and the 'defect' irrelevant.

>It  seemed that the ability to use large n-s, however, somehow was of
paramount
> importance, and you even suggested that Donovan use a rather obscure
> technique to vary k.

Okay, that was a distraction that I should have saved for another post.
Having found a easier way to accomplish the same, I retract it.

> Your latest algorithm is great, though, and I wish you had posted it the
> first time around.

I did not work it out until you challenged me.  I glad you like it.  It
will look even prettier if/when I rewrite it for nested scopes and remove
the workaround hacks.  (The intermediate version was, of course, very
helpful in arriving at this version.)

>I find it to important when explaining algorithms to  beginners that
extensibility and >generality of the algorithm should be taken care of
before speed.

If I still believed that program running speed came first, I would still be
programming in C.  The fact that I write in Python indicates different
priorities. Think about it.

Actually, correctness come first in my opinion.  In this regard, having
builtin lists and list comparison and being able to interactively type

>>> known_correct_function(n) == new_version(n) # and see
1 # ie, the thousand element lists are identical

was extremely helpful.  I hate to even think about how I would test
identical behaviour of three C versions.

>When I find myself in a position where I need to unroll loops (or even get
rid of >recursion), I'm already reprogramming the algorithm in C++.

Whereas I'm thinking about how to remove the recursion in a Python version
starting with
for k in range(k0, 0, -1):
I would not even think of rewriting in C until I had the generalized
iterative version giving a list == known corrrect list for at least two
values of each parameter.

Terry J. Reedy