CODEWITHSUNDEEP
pythonalgorithmrecursion
ladybird333
ladybird333

Reputation: 33

Anagrams code resulting in infinite results

I need to generate anagrams for an application. I am using the following code for generating anagrams

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

The code above works in general. However, it prints infinite results when the following string is passed

str = "zzzzzzziizzzz"
print anagrams(str)

Can someone tell me where I am going wrong? I need unique anagrams of a string

Upvotes: 2

Views: 92

Answers (3)

M Oehm
M Oehm

Reputation: 29126

Others have pointed out that your code produces 13! anagrams, many of them duplicates. Your string of 11 z's and 2 i's has only 78 unique anagrams, however. (That's 13! / (11!·2!) or 13·12 / 2.)

If you want only these strings, make sure that you don't recurse down for the same letter more than once:

def anagrams(s):
    if len(s) < 2:
        return s
    else:
        tmp = []
        for i, letter in enumerate(s):
            if not letter in s[:i]:
                for j in anagrams(s[:i] + s[i+1:]):
                    tmp.append(letter + j )
        return tmp

The additional test is probably not the most effective way to tell whether a letter has already been used, but in your case with many duplicate letters it will save a lot of recursions.

Upvotes: 1

John La Rooy
John La Rooy

Reputation: 304215

There isn't infinte results - just 13! or 6,227,020,800

You're just not waiting long enough for the 6 billion results.

Note that much of the output is duplicates. If you are meaning to not print out the duplicates, then the number of results is much smaller.

Upvotes: 0

Reblochon Masque
Reblochon Masque

Reputation: 36682

This is not an infinity of results, this is 13!(*) words (a bit over 6 billions); you are facing a combinatorial explosion.

(*) 13 factorial.

Upvotes: 4

Related Questions