Drawing Blanks

Premature Optimization is a Prerequisite for Success

Integer Partitions

with 3 comments

Today I give you the algorithm for generating integer partitions, which is used for anagram generation. Behold:

        List<int> GetNextPartition(List<int> p)
        {
            //mutates the list p to produce the next partition in
            // reverse lex order, first partition being a single number n, 
            // and the last one is n ones.
            int len  = p.Count;
            //there is a tail of ones. count it and cut it off.
            int tailLen = 0;
            while(tailLen < len && p[len - tailLen - 1] == 1)
            {
                p.RemoveAt(len - tailLen - 1);
                tailLen++;
            }
            if (p.Count == 0) //all values were 1, this is the last partition
                return null;
            //all numbers in p are now > 1.
            //decrement the last (smallest) element;
            int cutValue = p[p.Count - 1] - 1;
            p[p.Count - 1] = cutValue;

            //now we have to add back all the 1s that we cut off
            int remainder = tailLen + 1;
            //append the 1s, clumped into groups of non-increasing size.
            //e.g. 3,1,1,1,1 becomes 2,2,2,1 (which in turn will become 2,2,1,1,1).
            while (remainder > 0)
            {
                if (remainder > cutValue)
                {
                    p.Add(cutValue);
                    remainder -= cutValue;
                }
                else
                {
                    p.Add(remainder);
                    remainder = 0;
                }
            }
            return p;
        }

OTHER POSTS IN THE “ROAD TO FULL ANAGRAMS”¬†SERIES:

https://bbzippo.wordpress.com/2009/11/27/inside-xworder-the-road-to-full-anagrams/

https://bbzippo.wordpress.com/2009/12/06/inside-xworder-the-road-to-full-anagrams-2/

https://bbzippo.wordpress.com/2009/12/18/integer-partitions/

https://bbzippo.wordpress.com/2010/01/06/generating-combinations/

Advertisements

Written by bbzippo

12/18/2009 at 4:06 am

Posted in programming

3 Responses

Subscribe to comments with RSS.


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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: