15

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.

Blckknght
  • 100,903
  • 11
  • 120
  • 169
gran_profaci
  • 8,087
  • 15
  • 66
  • 99
  • 1
    It looks like you have an indentation error here, also, it's worth pointing out that this code is re-inventing the wheel. There's already `itertools.permutations` in the standard library :-) -- Though that doesn't help you understand this code. – mgilson Dec 23 '12 at 04:09
  • What do you mean by "he" and "this man"? – David Robinson Dec 23 '12 at 04:10
  • 1
    @DavidRobinson I think that was just a "cute" way of asking what was going on in the code. I've rewritten the question to ask directly for an explanation, which I think was what the questioner wanted (and has received). – Blckknght Dec 23 '12 at 04:28

2 Answers2

56

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
Mark Byers
  • 811,555
  • 193
  • 1,581
  • 1,452
7

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']
tbradley22
  • 1,535
  • 2
  • 15
  • 14