0xDE (11011110) wrote,

Integer partitions

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.
Tags: algorithms, combinatorial enumeration, number theory, partitions, python
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded