Write a program to display all the anagrams for "abcdef" in Python

Question

My friend wrote a code to display all anagrams for "abcdef" in python. But in this code, I couldn't understand how the recursive procedure works anagrams = get_list_of_anagrams(''.join(tmp_list)) How does the function call itself?

def get_list_of_anagrams(s):
    if len(s)==0:
        return ['']
    all_chars = list(s)
    unique_chars = list(set(s))
    anagrams_list = []
    for char in unique_chars:
        tmp_list = list(all_chars)
        tmp_list.remove(char)
        anagrams = get_list_of_anagrams(''.join(tmp_list))
        for i in range(len(anagrams)):
            anagrams[i] = char+anagrams[i]
        anagrams_list += anagrams
    return anagrams_list

When I try to print every thing till anagrams = get_list_of_anagrams(''.join(tmp_list)

def get_list_of_anagrams(s):
    if len(s)==0:
        return ['']
    all_chars = list(s)
    unique_chars = list(set(s))
    anagrams_list = []
    for char in unique_chars:
        tmp_list = list(all_chars)
        tmp_list.remove(char)
        anagrams = get_list_of_anagrams(''.join(tmp_list))



print get_list_of_anagrams('abc')

I get the following out put.

For the following code:

def get_list_of_anagrams(s):
    if len(s)==0:
        return ['']
    all_chars = list(s)
    unique_chars = list(set(s))
    anagrams_list = []
    for char in unique_chars:
        tmp_list = list(all_chars)
        tmp_list.remove(char)
        anagrams = get_list_of_anagrams(''.join(tmp_list))
        print anagrams
        for i in range(len(anagrams)):
            anagrams[i] = char+anagrams[i]
        anagrams_list += anagrams
    return anagrams_list  

print get_list_of_anagrams('abc')

I get the following output:

can some one explain me why the above output is of this pattern?

Answer 1

Life is short use libraries:

import itertools
d = 'abc'
e = len(d)
j = list()

for p in itertools.permutations(d, e):
    print p

('a', 'b', 'c')
('a', 'c', 'b')
('b', 'a', 'c')
('b', 'c', 'a')
('c', 'a', 'b')
('c', 'b', 'a')

Answer 2

Tracing through:

def get_list_of_anagrams(s):
    # base case - empty string, return empty
    if len(s)==0:
        return ['']

    # figure out which characters are available
    all_chars    = list(s)       # may have repeats
    unique_chars = list(set(s))  # no repeats

    # prepare to store all results
    anagrams_list = []

    # for each unique character
    for char in unique_chars:
        # remaining unused characters
        tmp_list = list(all_chars)
        tmp_list.remove(char)

        # recurse: get all anagrams of remaining characters
        anagrams = get_list_of_anagrams(''.join(tmp_list))

        # prefix each result with picked character
        for i in range(len(anagrams)):
            anagrams[i] = char+anagrams[i]

        # add to overall results
        anagrams_list += anagrams

    # return all results
    return anagrams_list

I would rewrite it a bit, like

def get_list_of_anagrams(s):
    anagrams = []

    remaining = list(s)
    for char in sorted(set(s)):
        remaining.remove(char)
        if remaining:
            # recurse: get all anagrams of remaining characters
            for anagram in get_list_of_anagrams(remaining):
                # prefix each result with picked character
                anagrams.append(char + anagram)
        else:
            anagrams.append(char)
        remaining.append(char)

    # return all results
    return anagrams

So to find get_list_of_anagrams("abcdef"), you get

"a" + each(get_list_of_anagrams("bcdef"))
"b" + each(get_list_of_anagrams("acdef"))
"c" + each(get_list_of_anagrams("abdef"))
"d" + each(get_list_of_anagrams("abcef"))
"e" + each(get_list_of_anagrams("abcdf"))
"f" + each(get_list_of_anagrams("abcde"))

etc.

Answer 3

It's a Recursive function. For example the famous Fibonacci Sequence:

def fib(n):
    if n < 2:
        return n
    return fib(n-2) + fib(n-1)
print fib(10)

Check this question about recursive for more information.

Answer 4

The idea is, to find the anagrams of 'abc', first find all the anagrams of 'bc', which is done by first finding all anagrams of 'c', which is done by first finding all anagrams of ''.

So how do you find the anagrams of the "outer layer" given all the anagrams of the "inner layer"? Given all the anagrams of 'bc' (which are 'bc' and 'cb'), you can find all the anagrams of 'abc' by inserting a into each positions of 'bc' and 'cb'. In details:

# 'bc' will give these anagrams:
abc # insert 'a' at first position
bac # insert 'a' at second position
bca # insert 'a' at third position (also last)

# Similarly, 'cb' gives:
acb
cab
cba

So 2 anagrams of 'bc' give you 6 anagrams of 'abc'.

===

About your algorithm: it removes 1 character at each recursion (using tmp_list.remove(char)). At the base case where len(s)==0 (i.e. when all characters have been removed), it simply returns ''. Then proceeds to find the anagrams of 'f' using the logic above, then the anagrams of 'ef'.... and finally returns you the anagrams of abcdef.