0

I have found the following code from: Finding all possible permutations of a given string in python

it works nicely but I don't understand part of the loop that I've highlighted below:

def permutation(string, step=0):    
    if step == len(string):
        print("".join(string))
    for i in range(step, len(string)):
        print('step:', step, ' i: ', i)
        string_copy = [c for c in string]
        string_copy[step], string_copy[i] = string_copy[i], string_copy[step]
        # print(i, string_copy, step)
        permutation(string_copy, step+1)
        print('step:', step, ' step+1: ', step+1)
print(permutation('ABC'))

when I run it, I understand that the loop starts with i=0, step=0 and every time runs the function for list generated and "step+1". what I don't understand is that after printing the string (step+1=len(string)) how it goes back to step: 1 and then step: 1 and i: 2 in my example below? the output of code for "ABC". the red boxes are parts that I don't understand: enter image description here

Roshin Raphel
  • 2,612
  • 4
  • 22
  • 40
Fetona
  • 34
  • 6
  • 2
    You seem to be asking how _recursion_ works. If you search for this topic, you'll find a wealth of information is available. – paddy Sep 24 '20 at 03:07
  • no, I understand how it runs the function over and over. I just don't understand how the steps are decreased. when the code gets to permutation(string_copy, step+1) it runs the permutation function for string list and adds 1 to the step. but after this step and before going through the loop for the next iterator (i=1), step is changed to 1. I don't understand how does this happen? – Fetona Sep 24 '20 at 03:35
  • 3
    It seems you still don't understand how recursion works, and maybe stack / scope too. When you call any function (including the same function), its local variables (including its arguments) live in a new part of the stack. When the function returns, its own local values remain intact, and not be affected by the fact that a function was called. – paddy Sep 24 '20 at 03:59
  • 1
    It's the recursion. When the function calls itself (`permutation(string_copy, step+1)`), it's starting a _new copy_ of the function that starts over from the top of the function body with its very own independent arguments and local variables. And then when that copy calls itself, it creates yet another copy, and so on. All of the versions coexist without interfering with each other despite using the same names for stuff, like parallel dimensions. – Mark Reed Sep 24 '20 at 13:35

0 Answers0