Week 3

This week I continued with my work on partitions. The multiset algorithm I had implemented earlier had bugs involving overgeneration and generating incorrect output for some cases. Those were fixed by adding a cache, although the problem of overgeneration remained. That can be fixed to an extent by sorting in the canonical order before we put it there but I would prefer if the implementation can be made a bit more robust. This algorithm was quite difficult to implement and thanks go out to smichr, haz and mwhansen for all their helpful comments and suggestions.

I also implemented a rather cute partitioning algorithm that breaks up numbers into powers of 2. This is referenced as an exercise in Knuth. In fact, since most of combinatorica’s functionality as far as permutations, partitions and subsets go, have been replicated, I am veering off into TAOCP’s exercises. These extend the theory developed in a rich and beautiful manner. A nice example is that of a partition lattice. This is basically a poset where the ordering between elements is decided on the basis of which majorizes the other. Majorization has been discussed earlier, so its a matter of generating all the partitions and figuring out an algorithm that can rapidly populate a lattice based this comparison measure. Comparisons between general partitions will be on the basis of their rank for now although a concept similar to majorization has been discussed for them in TAOCP.

Other things that were implemented this week was stuff related to restricted growth strings and Ferrers diagram which is a cute way to visualize a partition. RGS are fun because they are the basis of another type of gray codes. Currently I have implemented routines to extract the partition from the RGS, convert a partition to an RGS, enumerating all the RGS and ranking and unranking RGS. This will form the basis of stateful generation of lexicographically ordered partitions because I could not really find any other way of doing it cleanly.

Some pending work that I still need to do however is ranking and unranking ksubsets as well as their stateful generation. Once I have all of these things taken care of, hopefully I can move on to trees and graphs.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: