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.

I also added a readme file putting PADS into the public domain, and a tarball for easier downloading of the whole library.




Comments:

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