Printing to stdout gives the correct list, but appending to a list does not

Question

I working on this problem on leetcode:

Given a collection of distinct integers, return all possible permutations.

If I iteratively print my results I get the correct values. As soon as I add it to a list the results are incorrect. What is happening?

class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) == 1:
            return nums 

        permutations = list()
        import math
        max_swaps = math.factorial(len(nums))
        pair = [0,1]
        for i in range(max_swaps):
            if pair[1] == len(nums):
                pair[0] = 0
                pair[1] = 1
            p = self.swap(nums, pair[0], pair[1])
            print("Adding %s to the list" % p)
            permutations.append(p)
            pair[0] += 1
            pair[1] += 1
        return permutations

    def swap(self, nums, index1, index2):
        tmp = nums[index2]
        nums[index2] = nums[index1]
        nums[index1] = tmp
        return nums

I should get:

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

But instead I get:

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

You have a list full of references to *the same single list*, you don’t make copies anywhere. — jonrsharpe, Jun 22 '18 at 21:49

score 3 · Accepted Answer · answered Jun 22 '18 at 21:49

You keep adding a reference to the same list to permutations.

When you call:

permutations.append(p)

Python doesn't take a copy of the list, it adds a reference. You only have one list.

What you want to do is:

permutations.append(p[:])

Which will take a copy.

score 2 · Answer 2 · answered Jun 22 '18 at 21:49

2

When you return nums from swap, you're not making a copy, you're returning the same list that will be modified later. You can make a copy either at the return or when you append the list to your result.

answered Jun 22 '18 at 21:49

Mark Ransom

299,747
42
398
622

1

Personally, if the method was returning a copy I'd call it `swapped` instead of `swap`, following the "convention" of `sort` vs `sorted` and such. – jbch Jun 22 '18 at 21:53
@jbch You make a good point. I consider a function that modifies a list and also returns it to be a code smell. See https://stackoverflow.com/a/46796007/5987 – Mark Ransom Jun 22 '18 at 21:56
that's fair, I didn't mention it but I would also make an in-place function return None, now that you mention it. – jbch Jun 26 '18 at 15:45

score 1 · Answer 3 · answered Jun 22 '18 at 21:50

This is a common bug in a lot of code. The bug you're seeing here is a symptom of having the values returned from swap be the same as nums. This means that you're appending nums over and over into the permutations list. If you were to print the entire permutations list instead of only p you'd see that they were always the same.

The solution is rather simple: At some point in your code (likely in swap or something) you need to make a copy of the nums list.

Printing to stdout gives the correct list, but appending to a list does not

3 Answers3