usage of the append function of list in python

Question

class Solution:    
    # @param num, a list of integer
    # @return a list of lists of integers
        def permute(self, num):
            self.res = [];
            self.dfs(num, 0)
            return self.res

        def dfs(self, num, level):
            if level == len(num):
                self.res.append(num)
                print(num)
                return
            for i in range(level, len(num)):
                num[i], num[level] = num[level], num[i]
                self.dfs(num, level+1)
                num[i], num[level] = num[level], num[i]

The above code is used to generate all permutations given a collection of numbers. For example, num = [1, 3] The result will be: [1 3], [3, 1]

But there is a bug for the above code that I don't understand, which is self.res.append(num). If I change it to self.res.append(num[:]), then the code is correct. Can anyone explain why?

Using self.res.append(num), the result is:

[1, 3], [1, 3]

Using self.res.append(num[:]), the result is:

[1, 3], [3, 1]

Antti Haapala · Accepted Answer · 2014-05-29 18:14:19Z

4

The elements of a python list are references to other objects. When you append using self.res.append(num), the list is grown by 1 element, and the last element is set to refer to the object pointed to by num.

Now in the first case, there are 2 references to the same list object. As self.res[0] and self.res[1] refer to the same object, all changes performed through either are also visible through the other.

In the second case, using num[:], [:] operator makes a new list that is copy of the original.

For general algorithm for creating all permutations of a given collection of elements, use the itertools.permutations:

>>> from itertools import permutations
>>> print(list(permutations([1, 3])))
[(1, 3), (3, 1)]

edited May 29, 2014 at 18:14

answered May 29, 2014 at 17:57

Antti Haapala

135k23 gold badges297 silver badges349 bronze badges

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

2 Comments

Serge Ballesta Over a year ago

You could also use list(num) to obtain a copy of num.

Antti Haapala Over a year ago

True. The [:] is the general way to make a copy of a sequence if mutable, whereas list() is a way to make a list with elements of an iterable

Collectives™ on Stack Overflow

usage of the append function of list in python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related