Q:

Please explain this algorithm to get all permutations of a String

The following code generates all the permutations for a string:
def permutations(word):
    if len(word)<=1:
        return [word]

    #get all permutations of length N-1
    perms=permutations(word[1:])
    char=word[0]
    result=[]
    #iterate over all permutations of length N-1
    for perm in perms:
        #insert the character into every possible location
        for i in range(len(perm)+1):
            result.append(perm[:i] + char + perm[i:])
    return result

Can you explain how it works? I don't understand the recursion.

A:

The algorithm is:

Remove the first letter
Find all the permutations of the remaining letters (recursive step)
Reinsert the letter that was removed in every possible location.

The base case for the recursion is a single letter. There is only one way to permute a single letter.
Worked example
Imagine the start word is bar.

First remove the b.
Find the permuatations of ar. This gives ar and ra.
For each of those words, put the b in every location:

ar -> bar, abr, arb
ra -> bra, rba, rab

A:

I've written the steps out for a string of length 2 and a string of length 3 below.
permutations('ab')
len('ab') is not <= 1 
perms = permutations of 'b'
len('b') <= 1 so return 'b' in a list
perms = ['b']
char = 'a'
result = []
for 'b' in ['b']:
    for 0 in [0,1]:
        result.append('' + 'a' + 'b')
    for 1 in [0,1]:
        result.append('b' + 'a' + '')
result = ['ab', 'ba'] 

permutations('abc')
len('abc') is not <= 1
perms = permutations('bc')
perms = ['bc','cb']
char = 'a'
result =[]
for 'bc' in ['bc','cb']:
    for 0 in [0,1,2]:
        result.append('' + 'a' + 'bc')
    for 1 in [0,1,2]:
        result.append('b' + 'a' + 'c')
    for 2 in [0,1,2]:
        result.append('bc' + 'a' + '') 
for 'cb' in ['bc','cb']:
    for 0 in [0,1,2]:
        result.append('' + 'a' + 'cb')   
    for 1 in [0,1,2]:
        result.append('c' + 'a' + 'b')   
    for 2 in [0,1,2]:
        result.append('cb' + 'a' + '')
result = ['abc', 'bac', 'bca', 'acb', 'cab', 'cba']  

