Simple anagram or permutation generator in Python

Question

In preparation for a job interview I decided to try and implement the classic find all anagrams of a given string solution. I wanted to see if I could translate a javascript solution into python. This was my attempt:

def anagrams(word):
 if len(word) < 2:
 return word
 else:
 tmp = []
 for i, letter in enumerate(word):
 for j in anagrams(word[:i]+word[i+1:]):
 tmp.append(j+letter)
 return tmp
if __name__ == "__main__":
 print anagrams("abc")

• SylvainD: It probably makes the exercise less interesting but you could have a look at itertools.permutations
• Janne Karila: This returns duplicates if any letter appears more than once in word.

Answer 1

Your python code is neat, simple and easy to understand (so generally it's good); and yet, something in me doesn't like the use of so many temporary arrays. How about using a generator?

def anagrams(word):
 """ Generate all of the anagrams of a word. """ 
 if len(word) < 2:
 yield word
 else:
 for i, letter in enumerate(word):
 if not letter in word[:i]: #avoid duplicating earlier words
 for j in anagrams(word[:i]+word[i+1:]):
 yield j+letter 
if __name__ == "__main__":
 for i in anagrams("acbcddd"):
 print i

I (now) filtered out all duplicates which is almost certain your original intention and is standard in all anagram problems. I did this by seeing if the same letter was already earlier in the word in which case we will have already generated this anagram.

You would have to do the same, or get rid of duplicates in your list for example by doing

return list(set(tmp))

instead of your current return from anagrams.

• nicholaschris: As mentioned in the comments, the original code returns duplicates if any letter appears more than once. Does this code have the same issue?
• Michael: @nicholaschris ... err... hummm...mutter mutter... not any more ;-) Thanks.