Drawing Blanks

Premature Optimization is a Prerequisite for Success

Inside Xworder: the road to full anagrams

with 3 comments

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);            

            var headAnagrams = FindSubanagramsExact(s, partitionHead);

            if (!partitionTail.Any())
            {
                foreach (string a in headAnagrams)
                    yield return a;
            }
            else
            {
                foreach (string headAnagram in headAnagrams)
                {
                    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.

CONTINUE READING:

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

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

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

About these ads

Written by bbzippo

11/27/2009 at 7:36 pm

Posted in programming

3 Responses

Subscribe to comments with RSS.

  1. [...] a comment » Now that I have described the high-level approach to full anagrams that is used by Xworder, the next thing I’d like to tell is how it finds [...]

  2. [...] » Today I give you the algorithm for generating integer partitions, which is used for anagram generation. [...]

  3. [...] leave a comment » This little function will conclude The Road to Full Anagrams http://bbzippo.wordpress.com/2009/11/27/inside-xworder-the-road-to-full-anagrams/ [...]


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

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: