Python recursive permutation program explanation

Question

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

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

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 · Accepted Answer · 2017-10-01 18:57:45Z

 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.

Collectives™ on Stack Overflow

Python recursive permutation program explanation

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related