Why is my code mutating the contents of a list in python?

Question

I am trying to generate all permutations for a given set. On each callback of my code, the contents of the array change for some reason, when I am using the append function. Can someone point me in the right direction?

class Solution(object):
    def permute(self, nums):
        res = []
        self.generate_permutations(nums, res, 0, len(nums)-1)
        return res

    def generate_permutations(self, nums, res, l, r):
        if l == r:
            res.append(nums)

        for i in range(l, r+1):
            nums[i], nums[l] = nums[l], nums[i]
            print('res', res)
            self.generate_permutations(nums, res, l+1, r)
            nums[l], nums[i] = nums[i], nums[l]

By the way, return res.append is going to return None and you never capture the recursive return value, but itertools is your friend, and you should learn that method to make permutations — OneCricketeer
– OneCricketeer, Commented Jan 24, 2017 at 2:34
@cricket_007 no idea why i had return res.append in there. But im not using itertools because this is for algorthm study. Its generating the permutations correctly, but theres a python gotcha thats changing the values — driftdrift
– driftdrift, Commented Jan 24, 2017 at 2:36
Why are you objecting to creating a copy each time? Do you want n-references to the same permutation in your list, or n distinct permutations? — hpaulj
– hpaulj, Commented Jan 24, 2017 at 3:07

hpaulj · Accepted Answer · 2017-01-24 08:17:10Z

Maybe this simplified generator will make the problem clearer:

def gen(num):
    for i in range(3):
        num.append(i)
        yield num

It generates a growing list:

In [119]: g=gen([])
In [121]: next(g)
Out[121]: [0]
In [122]: next(g)
Out[122]: [0, 1]
In [123]: next(g)
Out[123]: [0, 1, 2]

But if I collect the results in a list, I get repeats

In [125]: [i for i in gen([])]
Out[125]: [[0, 1, 2], [0, 1, 2], [0, 1, 2]]

Instead I need to collect copies

In [126]: [i[:] for i in gen([])]
Out[126]: [[0], [0, 1], [0, 1, 2]]

The repeats may be more obvious if I look at the id of each element

In [129]: [id(i) for i in alist]
Out[129]: [2881121580, 2881121580, 2881121580]

or if I modify one element of the list (and end up modifying all)

In [130]: alist[0].append(10)
In [131]: alist
Out[131]: [[0, 1, 2, 10], [0, 1, 2, 10], [0, 1, 2, 10]]

=================

With your function, saving nums[:] to res:

def generate_permutations(nums, res, l, r):
        if l == r:
            res.append(nums[:])        # <=== change
        for i in range(l, r+1):
            nums[i], nums[l] = nums[l], nums[i]
            generate_permutations(nums, res, l+1, r)
            nums[l], nums[i] = nums[i], nums[l]
In [158]: res=[];nums=[1,2,3]
In [159]: generate_permutations(nums, res,0,2)
In [160]: res
Out[160]: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

Collectives™ on Stack Overflow

Why is my code mutating the contents of a list in python?

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