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.
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, arbra -> bra, rba, rab
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']
