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






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 https://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 )

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: