Google+ Followers

07 December 2011

Anagrams

Anagrams are words that have the same set of letters but in a different order. For example, "modern" and "normed" are anagrams; so are "algorithm" and "logarithm". Good Scrabble players are adept at anagram creation.

From a programmatic point of view, anagrams can be created by first extracting the characters in a word, permuting those characters, and then finding which permutations are real words.

Let's start by getting the characters in a word:

In[1]:= chars = Characters["tame"]
Out[1]= {t,a,m,e}

Permute the characters.

In[2]:= p = Permutations[chars]
Out[2]= {{t,a,m,e},{t,a,e,m},{t,m,a,e},{t,m,e,a},{t,e,a,m},{t,e,m,a},{a,t,m,e},{a,t,e,m},{a,m,t,e},{a,m,e,t},{a,e,t,m},{a,e,m,t},{m,t,a,e},{m,t,e,a},{m,a,t,e},{m,a,e,t},{m,e,t,a},{m,e,a,t},{e,t,a,m},{e,t,m,a},{e,a,t,m},{e,a,m,t},{e,m,t,a},{e,m,a,t}}

Concatenate the characters in each list:

In[3]:= words = Map[StringJoin, p]
Out[3]= {tame,taem,tmae,tmea,team,tema,atme,atem,amte,amet,aetm,aemt,mtae,mtea,mate,maet,meta,meat,etam,etma,eatm,eamt,emta,emat}

Note that OutputForm of strings in Mathematica omits the double-quotes.

In[4]:= "string"
Out[4]= string

You can still see them using FullForm or InputForm.

In[5]:= FullForm[%]
Out[5]//FullForm= "string"

Now, which of these "words" are really words? You can select those that are in the dictionary. Those elements in words that are not in the dictionary will return {} when run against DictionaryLookup, so we omit those using !=.

In[6]:= Select[words, DictionaryLookup[#, IgnoreCase -> True]!={}&]
Out[6]= {tame,team,mate,meta,meat}

Note: you could substitute any list of words for DictionaryLookup[...] here including languages other than English; e.g.,

In[7]:= DictionaryLookup[All]
Out[7]= {Arabic,BrazilianPortuguese,Breton,BritishEnglish,Catalan,Croatian,Danish,Dutch,English,Esperanto,Faroese,Finnish,French,Galician,German,Hebrew,Hindi,Hungarian,IrishGaelic,Italian,Latin,Polish,Portuguese,Russian,ScottishGaelic,Spanish,Swedish}

So putting all the pieces together, we have the function Anagrams.

In[8]:= Anagrams[word_String]:= 
Module[{chars = Characters[word],words},
  words = Map[StringJoin, Permutations[chars]];
  Select[words, DictionaryLookup[#, IgnoreCase -> True]!={}&]]

In[9]:= Anagrams["elvis"]
Out[9]= {elvis,evils,levis,lives,veils}

In[10]:= Anagrams["instance"]
Out[10]= {instance,ancients,canniest}

The exercises include an example of a more direct approach to this problem, one that avoids the creation of permutations of the characters in the word.

In the next blog post we will put Anagrams to work in creating blanagrams, words that differ by one letter.

-- Excerpted from Programming with Mathematica: An Introduction, Cambridge University Press, 2013.



No comments:

Post a Comment