6
\$\begingroup\$

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")
\$\endgroup\$
  • 4
    \$\begingroup\$ It probably makes the exercise less interesting but you could have a look at itertools.permutations \$\endgroup\$ – SylvainD May 29 '14 at 20:07
  • \$\begingroup\$ This returns duplicates if any letter appears more than once in word. \$\endgroup\$ – Janne Karila May 30 '14 at 15:56
5
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ As mentioned in the comments, the original code returns duplicates if any letter appears more than once. Does this code have the same issue? \$\endgroup\$ – nicholaschris May 31 '14 at 12:33
  • \$\begingroup\$ @nicholaschris ... err... hummm...mutter mutter... not any more ;-) Thanks. \$\endgroup\$ – Michael May 31 '14 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.