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/
[…] 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 […]
Inside Xworder: the road to full anagrams 2 « Drawing Blanks
12/06/2009 at 11:36 pm
[…] » Today I give you the algorithm for generating integer partitions, which is used for anagram generation. […]
Integer Partitions « Drawing Blanks
12/18/2009 at 4:06 am
[…] 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/ […]
Generating Combinations « Drawing Blanks
01/06/2010 at 6:21 am