Behaviour of python lists in recursion

Question

The below code returns all possible permutations of the numbers provided.

class Solution:

  def permute(self, numbers, start, result):
        if start == len(numbers):
            print(numbers)
            result.append(numbers[:])
            return
        for i in range(start, len(numbers)):
            numbers[start], numbers[i] = numbers[i], numbers[start]
            self.permute(numbers, start + 1, result)
            numbers[start], numbers[i] = numbers[i], numbers[start]

  def solution(self, numbers):
        result = []
        if not numbers or len(numbers) == 0:
            return numbers
        self.permute(numbers, 0, result)
        return result

res1 = Solution().solution([1, 2, 3])
print(res1)

The final output for this instance will be

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

but when I slightly modify the permute function, the output is completely different

def permute(self, numbers, start, result):
        if start == len(numbers):
            print(numbers)
            result.append(numbers) #changing this line
            return
        for i in range(start, len(numbers)):
            numbers[start], numbers[i] = numbers[i], numbers[start]
            self.permute(numbers, start + 1, result)
            numbers[start], numbers[i] = numbers[i], numbers[start]

which gives the output

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

The program works when I use

result.append([x for x in numbers])

or

result.append(numbers[:])

but not when I use

result.append(numbers)

Can someone help me understand as to why this is happening ?

As in Karoly Horvath answer , when you do numbers[:] it creates a new array for you. — gipsy
– gipsy, Commented May 23, 2016 at 14:53

Karoly Horvath · Accepted Answer · 2016-05-23 14:47:58Z

2

If you don't create a copy of the object with the techniques you've described, you put the same object in the list again and again.

Here's a short example to illustrate the issue:

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

answered May 23, 2016 at 14:47

Karoly Horvath

96.7k11 gold badges123 silver badges181 bronze badges

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

1 Comment

sauvik Over a year ago

Thanks for the quick reply :)

Collectives™ on Stack Overflow

Behaviour of python lists in recursion

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related