 Shantanu Shady - 3 years ago 223
Python Question

# Python recursive permutation program explanation

I have a code that uses recursion to calculate the permutation of the characters of a string. I understand normal tail recursion and recursions for palindrome, factorial, decimal to binary conversion easily but i am having problem understanding how this recursion works, i mean how it actually works in the background, not just the abstract stuff from the higher level i get that.

here is the code

``````from __future__ import print_function

def permutef(s):
#print('\nIM CALLED\n')
out = []

if len(s) == 1:
out = [s]
else:
for i,let in enumerate(s):

#print('LETTER IS {} index is {}'.format(let, i))

#Slicing as not including that letter but includes every letter except that to perform the permutation

for perm in permutef( s[:i] + s[i+1:] ):

print(perm)

out += [let + perm]
return out

per = permutef('abc')

print('\n\n\n', per, '\n\n\n')
`````` I was writing in a paper each circle is for each letter and how the corresponding stack pops

here is the output screenshot i want to understand the nitty gritty about how this works in the background, but i can't seem to fathom the concept, very very thanks in advance. holdenweb
`````` 1  def permutef(s):
2      out = []
3      if len(s) == 1:
4          out = [s]
5      else:
6          for i,let in enumerate(s):
7              for perm in permutef( s[:i] + s[i+1:] ):
8                  print(perm)
9                  out += [let + perm]
10      return out
``````

The principle is fairly straightforward. A one-character string (line 3) only has one permutation, represented by a list containing that character (line 4). The permutations of longer strings are generated by taking each character in the string and permuting the remaining characters - a fairly classic recursive divide-and-conquer approach.

For problems like this the Python Tutor site can be useful to visualise the execution of your code. The link I've provided is pre-loaded with the code above, and you can step forwards and backwards through the code until you understand how it works.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download