Shantanu Shady 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')


enter image description here

I was writing in a paper each circle is for each letter and how the corresponding stack pops

Don't ask about my handwriting i know its awesome (sarcasm)

here is the output screenshot

enter image description here

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.

Answer Source
 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