# Drawing Blanks

Premature Optimization is a Prerequisite for Success

## Integer Partitions

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)
{
remainder -= cutValue;
}
else
{
remainder = 0;
}
}
return p;
}```

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

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

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