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

            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:

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