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 popped all the items out of. — Patrick Haugh
– Patrick Haugh, Commented Sep 17, 2018 at 13:32
Possible duplicate of How to generate all permutations of a list in Python — Sayse
– Sayse, Commented Sep 17, 2018 at 13:34
The res variable you define inside your recursive function is not the same as the one defined in main. — toti08
– toti08, Commented Sep 17, 2018 at 13:34
@toti08 since res is NOT defined in backtrack() it is the global one. — bruno desthuilliers
– bruno desthuilliers, Commented Sep 17, 2018 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
– bruno desthuilliers, Commented Sep 17, 2018 at 13:42

Duncan · Accepted Answer · 2018-09-17 13:43:53Z

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)]

Collectives™ on Stack Overflow

Python recursive function wont change list defined in main()

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related