Python: append() weird behavior during recursion

Question

I was writing the following program to generate all possible permutations from a given list.

def permute(self, nums: List[int]) -> List[List[int]]:

        def __permute(nums, n, chosen, perms):
            if len(perms) == n:
                print(perms)
            else:
                for i in range(n):
                    if chosen[i]:
                        continue
                    else:
                        chosen[i] = True
                        perms.append(nums[i])
                        __permute(nums, n, chosen, perms)
                        perms.pop()
                        chosen[i] = False
            
        n = len(nums)
        __permute(nums, n, [False]*n, [])

For example:

Input: [1,2,3]
Output:
  [1,2,3]
  [1,3,2]
  [2,1,3]
  [2,3,1]
  [3,1,2]
  [3,2,1]

Now this time, I want to add all permutations in a list and return it:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Here is my code:

def permute(self, nums: List[int]) -> List[List[int]]:

        def __permute(nums, n, chosen, perms,res):
            if len(perms) == n:
                res.append(perms)
            else:
                for i in range(n):
                    if chosen[i]:
                        continue
                    else:
                        chosen[i] = True
                        perms.append(nums[i])
                        __permute(nums, n, chosen, perms, res)
                        perms.pop()
                        chosen[i] = False
            
        n = len(nums)
        res = []
        __permute(nums, n, [False]*n, [], res)
        return res

Problem is, the output is full of empty lists.

Input: [1,2,3]
Output:
[
  [],
  [],
  [],
  [],
  [],
  []
]

I fixed the bug by replacing res.append(perms) by res.append(perms[:]) but I don't understand why it works.

I also printed the id() of each perms and noticed something weird:

>>> print(id(perms))
>>>
140093677843328
140093677843328
140093677843328
140093677843328
140093677843328
140093677843328
>>> print(id(perms[:]))
>>>
140689610181440
140689610145600
140689610145600
140689610145600
140689610145600
140689610145600

Does anyone have an explanation to this behavior?

Because you are always working with the same perms list. And your algorithm clears that list, perms.pop()... so at the end, you end up with a bunch of refernces to the same empty list. — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Jul 22, 2020 at 9:47
When res.append(perms), the list perms is given as a reference. This perms later becomes empty by perms.pop(). As a result, the returned values are all empty. — Kota Mori
– Kota Mori, Commented Jul 22, 2020 at 9:48

Sai · Accepted Answer · 2020-07-22 09:48:14Z

1

perms is the same object every time, but when you do perms[:] you are creating a copy of perms (which is a separate object from perms).

res (list) stores the reference to perms, so if change perms the same will be reflected on the list res.

But doing res[:] gives you a copy of perms (which is a different object) as mentioned above.

answered Jul 22, 2020 at 9:48

Sai

1,7001 gold badge9 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Python: append() weird behavior during recursion

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