Week 2

The last week I worked mainly on subsets, gray codes and partitions.

Most of the functionality for subsets and gray codes is complete and a lot of progress has been made on the partitions front as well. Since last week Chris Smith updated the integer partition algorithm to include compositions as well. So apart from listing all the partitions, it also lists partitions of a specific size as well as partitions whose elements don’t exceed a particular value.

Today I wrote the multiset partitions algorithm prescribed in Knuth. This algorithm effectively generates multipartitions in decreasing lexicographic order. Apart from that, I implemented functionality for generating restricted growth strings from partitions and generating partitions from restricted growth strings. My next task will be to investigate the relationships between Gray codes and partitions. My primary reference for this is a paper by Frank Ruskey who demonstrates the construction of a simple recursive gray code which utilizes the restricted growth strings of the partition.

Regarding gray codes themselves, I basically implemented a class that describes the basic functionality of a binary reflected gray code. Various tasks such as generating the next and previous gray code, ranking and unranking, etc have been implemented. Other gray code implementations need only inherit the gray code class and override the relevant functions. Functionality demonstrating the interplay between gray codes and subsets has also been implemented. The additions to subsets have been quite comprehensive. You can generate subsets in a binary order, lexicographically and gray code ordered. Ranking and unranking can also be done in a similar manner. Functionality to generate ksubsets has also been implemented. Generating, ranking and unrankng ksubsets is still incomplete and is currently my next task that I hope to undertake.

In the midst of all this, I will need to clean up my commit history for permutations and add tests for the partitions branch. Hopefully I will get on to trees later this week.

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: