What's the point of using [:]

Question

I was looking at someone's solution to backtracking using the heap's algorithm using Python3 today. The solution is below:

def permute(self, nums):
    def backtrack(start, end):
        if start == end:
            ans.append(nums[:])
        for i in range(start, end):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start+1, end)
            nums[start], nums[i] = nums[i], nums[start]

    ans = []
    backtrack(0, len(nums))
    return ans

Now I am looking at the line ans.append(nums[:]), What's the point of writing nums[:]? Won't writing nums function correctly?

One common reason is to make a *copy* of a list, instead of just getting a reference to it. — Some programmer dude, Jul 15 '19 at 00:50

score 7 · Answer 1 · answered Jul 15 '19 at 00:50

Consider the following

>>> a = [1,2,3]
>>> b = [a]
>>> b[0].append(4)
>>> a
[1, 2, 3, 4]

As you can see, that modifying b[0] modifies a, because you have stored the object a in b, not just the values of a. Using [:] makes a copy of the list, so.

>>> a = [1,2,3]
>>> b = [a[:]]
>>> b[0].append(4)
>>> a
[1, 2, 3]

So the point is to pass the values, not the object itself.

Mark · Accepted Answer · 2019-07-15T00:57:56.470

No, it's not the same because in the for loop you are mutating nums

 nums[start], nums[i] = nums[i], nums[start]

If you append a reference to nums to your answer rather than an independent copy, you will be mutating all the asnwer's sub-elements and end up with a list of identical permutations all reflecting the final value. You can simply try that and see the results:

def permute(nums):
    def backtrack(start, end):
        if start == end:
            ans.append(nums)
        for i in range(start, end):
            # changing sums which will be reflected in all
            # references to nums in the ans array
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start+1, end)
            nums[start], nums[i] = nums[i], nums[start]

    ans = []
    backtrack(0, len(nums))
    return ans

permute([1, 2, 3])

All the same:

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

You can confirm they all point to the same object in memory:

l = permute([1, 2, 3])
[id(el) for el in l]

> [140539119291912, # all the same reference
   140539119291912,
   140539119291912,
   140539119291912,
   140539119291912,
   140539119291912]

By using ans.append(nums[:]) you make a copy so further mutations of nums don't affect the combinations you already have.

What's the point of using [:]

2 Answers2