totalcount = 0
res = []

def permute(nums):
    backtrack(nums, [])

def backtrack(nums, path):
    global totalcount
    totalcount  = 1
    if not nums:
        res.append(path)
    for x in range(len(nums)):
        #res.append(x)
        backtrack(nums[:x] nums[x 1:], path [nums[x]])

permute([1,2,3])

This is the code to return the permutations of a list of numbers, in my case [1, 2, 3]. I'm trying to trace the recursive calls to view the logic flow, but I just can't wrap my mind around it. When I commented in res.append(x) to figure out why I see this:

 [0, 0, 0, [1, 2, 3], 1, 0, [1, 3, 2], 
  1, 0, 0, [2, 1, 3], 1, 0, [2, 3, 1], 
  2, 0, 0, [3, 1, 2], 1, 0, [3, 2, 1]]

Also totalcount is 16 here, and I'm not sure why this function ran a total of that many times.

My questions are :

1. When backtrack is called for the first time, x=0. but of course it calls backtrack again, so in those calls, x goes to zero again. Following nums[:x] nums[x 1:], path [nums[x]] in this logic, I can see where [1,2,3] comes from (and before [1,2,3] the x values are 0,0,0 as I expected). But then all those inner calls should finish and then X should be two right? so doesn't that mean the next item in res should be [2,1,3]? I would expect this to just output res = [1,2,3],[2,1,3],[3,1,2], but it is indeed correctly giving the remaining permutations where 1 is first and 2 is first and 3 is first. How?
2. Why are there sometimes 3 instead of 2 values before a permutation set? Why are the values what they are? I suppose if I could understand these things I would understand a lot more about recursion and backtracking, but I've been trying to trace this out on paper for a long time and I am getting no closer.
3. What is the true order of these calls? if it runs 16 times, what are the values of the different variables in it on those runs?

CodePudding user response：

I logged the calls:

backtrack([1, 2, 3], [])
    backtrack([2, 3], [1])
        backtrack([3], [1, 2])
            backtrack([], [1, 2, 3])
        backtrack([2], [1, 3])
            backtrack([], [1, 3, 2])
    backtrack([1, 3], [2])
        backtrack([3], [2, 1])
            backtrack([], [2, 1, 3])
        backtrack([1], [2, 3])
            backtrack([], [2, 3, 1])
    backtrack([1, 2], [3])
        backtrack([2], [3, 1])
            backtrack([], [3, 1, 2])
        backtrack([1], [3, 2])
            backtrack([], [3, 2, 1])

Obtained with this decorator:

def log(func):
    depth = 0
    def logging_func(*args):
        nonlocal depth
        print('    ' * depth  
              func.__name__   '(' 
              repr(args)[1:-1]   ')')
        depth  = 1
        result = func(*args)
        depth -= 1
        return result
    return logging_func

Just copy that into your code and apply it to your backtrack:

@log
def backtrack(nums, path):
    ...

Try it online!

CodePudding user response：

Rather than answer your questions, I hope I can give you a technique that will let you find the answers for yourself. Consider adding a breakpoint() call to your code. It's a built-in that will put you in the interactive debugger.

totalcount = 0
res = []
def permute(nums):
    backtrack(nums, [])
def backtrack(nums, path):
    global totalcount
    totalcount  = 1
    if not nums:
        res.append(path)
    for x in range(len(nums)):
        #res.append(x)
        backtrack(nums[:x] nums[x 1:], path [nums[x]])
breakpoint()
permute([1,2,3])

Once you are in the interactive debugger, you can use the h command to list the available commands or h <command> to get help on a command. Basically, you need to just use the s command to step through your code.