Python programmers should be familiar with the following idiom:

>>> "A" * 3
"AAA"

It can be used to create pre-allocated lists, mimicking arrays.

>>> [0] * 3
[0, 0, 0]
>>> [None] * 3
[None, None, None]

Thus, to a pre-allocated nested list, i.e. a 2-dimensional array representing a matrix, the first thing that came to my mind is:

>>> [[0] * 3] * 3
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

But that is wrong, unfortunately. Though it might not be obvious at first, assigning value to an entry changes the values in every row.

>>> a[0][0] = 1
[[1, 0, 0],
 [1, 0, 0],
 [1, 0, 0]]

It actually turns out that the * operator doesn't create copies of a specified object, but rather repeats the reference to that same object. This explains why it is no issue when the created objects are immutable. It doesn't matter whether there are multiple references to the same immutable object; the object's state cannot be changed so there is no harm. The only thing you can do is to change the reference to another object entirely.

>>> a = ["A"] * 3
["A", "A", "A"]
>>> a[0] = "B"
["B", "A", "A"]

On the other hand, mutable objects are modifiable. When the state of a mutable object is altered, all references to that object will reflect that changes.

The gotcha is perhaps hardly observable because most Python's built-in types are immutable. List and other container types are mutable, however. Therefore when you create nested lists, i.e. list of lists, the issue is apparent.

To properly create pre-allocated lists, use list comprehension instead:

>>> [0 for x in range(3)]
[0, 0, 0]

And for nested lists:

>>> m = [[0 for x in range(3)] for x in range(3)]
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
>>> m[0][0] = 1
[[1, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

Jul 03, 2011