# Drawing Blanks

Premature Optimization is a Prerequisite for Success

## Inside Xworder: the road to full anagrams

What’s a full anagram? It’s one or more words that can be built by rearranging all letters from the given set. E.g. “Clint Eastwood” = “old west action” = “cows and toilet”, “Paul McCartney” = “clean up my cart” = “my nuclear pact”.

I’m going to present some algorithms that Xworder uses to generate them. I’ll start with a function that generates anagrams matching the given integer partition. What’s an integer partition?
4 = 2 + 2 = 2 + 1 + 1 = 1 + 3 = … – these are partitions of 4. So let’s say we have 4 letters. We can potentially build two two-letter words, one one-letter word and one three-letter word, and so on.

Here’s the function that builds all anagrams of the given string matching the given partition:

```        IEnumerable<string> FindFullAnagrams(string s, IEnumerable<int> partition)
{
int partitionHead = partition.First();
var partitionTail = partition.Skip(1);

if (!partitionTail.Any())
{
foreach (string a in headAnagrams)
yield return a;
}
else
{
{
string remainder = SubtractString(s, headAnagram);
foreach (string a in FindFullAnagrams(remainder, partitionTail))
yield return string.Concat(headAnagram, " ", a);
}
}
}```

Now, in order to actually generate anagrams, we need to implement just a couple of things: actually learn how to generate integer partitions, and then implement IEnumerable<string> FindSubanagramsExact(string s, int length) that finds words of the given length that can be built out of the string s.

Stay tuned.

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

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

Written by bbzippo

11/27/2009 at 7:36 pm

Posted in programming