Today's mail included the latest fascicle of Knuth's AOCP volume 4, so rather than getting any real work done I had some fun implementing the partition generation algorithms he lists; I added the resulting implementation to PADS. Knuth gives a nonrecursive algorithm for listing all partitions of n in revlex order, in constant time per partition, but doesn't seem to mention the similarly efficient recursive algorithm, which I first encountered two years ago, and which can be trivially modified to produce either lex or revlex order. Unless it's buried in the exercises somewhere... I included both algorithms in my implementation. Note that the ASPN version of the recursive algorithm takes $$O(n)$$ time per partition, because it copies the list each time, but this can easily be reduced to $$O(1)$$ per partition as I do in the new implementation.

leonardo_m: Reinventing the weel
2006-07-01T23:38:14Z

To solve a problem I created another integer partition Python program from scratch:

http://leonardo-m.livejournal.com/6514.html

It has required two hours of thinking or more, and then their Pascal version, translated to Pascal, is about twice faster than mine... (Your blog is very interesting, I am reading it all now)

None: Interesting post
2007-02-03T23:15:48Z

Your article is very informative and helped me further.

Thanks, David