Python recursive function wont change list defined in main()

Question

Here I wrote a recursive function to find the permutation of a list.

def backtrack(arr,tmp):
   if len(tmp)==len(arr):
       res.append(tmp)
       #==print res here==
       print(res)
   else:
       for i in range(len(arr)):
           if arr[i] in tmp: continue
           tmp.append(arr[i])
           backtrack(arr,tmp)
           tmp.pop()
if __name__ == '__main__':
   points=[1,2,3]
   res=[]
   tmp=[]
   backtrack(points,tmp)
   print(res)
   #code result
   #[[1, 3, 2], [1, 3, 2]]
   #[[2, 1, 3], [2, 1, 3], [2, 1, 3]]
   #[[2, 3, 1], [2, 3, 1], [2, 3, 1], [2, 3, 1]]
   #[[3, 1, 2], [3, 1, 2], [3, 1, 2], [3, 1, 2], [3, 1, 2]]
   #[[3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1]]
   #[[], [], [], [], [], []]

I have no idea why the list 'res' defined in main() wont be updated when we pass it to a recursive function. Any suggestion about how to update 'res'?

But it is being changed. It goes from being empty to having six items in it. Each of those items is an empty list because they're all actually the same item: the list `tmp`, which you've `pop`ped all the items out of. — Patrick Haugh, Sep 17 '18 at 13:32
Possible duplicate of [How to generate all permutations of a list in Python](https://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list-in-python) — Sayse, Sep 17 '18 at 13:34
The `res` variable you define inside your recursive function is not the same as the one defined in main. — toti08, Sep 17 '18 at 13:34
@toti08 since `res` is NOT defined in `backtrack()` it _is_ the global one. — bruno desthuilliers, Sep 17 '18 at 13:40
Just for the sake of correctness: you say (about `res`) " when we pass it to a recursive function", but you are NOT passing it anywhere, you're relying on a global (which is plain evil BTW). — bruno desthuilliers, Sep 17 '18 at 13:42
Also, you may want to learn the proper use of `for` loops in Python - you don't need this `range(len(arr))` nor `arr[i]`, you can get the items directly ie `for item in ["a", "b", "c"]: print(item)` — bruno desthuilliers, Sep 17 '18 at 13:44
And finally: read this: https://nedbatchelder.com/text/names.html — bruno desthuilliers, Sep 17 '18 at 13:45

Duncan · Accepted Answer · 2018-09-17T13:43:53.200

When you do:

res.append(tmp)

you are appending to the global list res a reference to the list tmp. Any future changes to tmp will be visible through res as it just contains multiple references to the same tmp list.

Instead you probably want to append a copy of tmp:

res.append(list(tmp))

Make that change and your output is now:

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

Alternatively you could convert the tmp list into a tuple:

res.append(tuple(tmp))

If you do that the option is then identical to the output returned by itertools.permutations:

>>> import itertools
>>> list(itertools.permutations([1,2,3]))
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

Python recursive function wont change list defined in main()

1 Answers1