Difference between 2 Ways of List Comprehensions in Python?

Question

I was using dynamic programming to implement the Matrix_Chain Problem, i.e. figure out the minimum number of multiplications to be done in matrix multiplication via parenthesizing. My code was not working until I changed the way of initializing list m. Could someone explain why, even when m = [[0]*n]*n and m = [[0 for x in range(n)] for x in range(n)] make seemingly identical list, m = [[0]*n]*n will results in matrix entry not being correctly updated to the minimum cost?

I made list m = [[0]*5]*5 and printed

for a in m:
  print(a)

I made list n = [[0 for x in range(5)] for x in range(5)] and also printed in the same way. The results are identical.

import sys
def Matrix_Chain (p, n):

  m = [[0]*n]*n #problematic step

  for i in range (1,n):
    m[i][i] =0

  for L in range(2, n):
     for i in range(1,n-L+1):    
        j = i + L -1
        m[i][j] = sys.maxsize

        for k in range (i, j):
        q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
        if q <  m[i][j]:
          m[i][j] = q
   return m[1][n-1]

For argument p = [1,2,3,4] and n = 4, I expect to see 18, the minimum number of multiplications. However, the m = [[0]*n]*n way will return 9223372036854775807, which is the sys.maxsize. The m = [[0 for x in range(n)] for x in range(n)] way returns the correct answer 18.

Welcome to Stack Overflow. There seems to be a lot of non-essential information here. Can you boil your question down to a [mcve]? See [ask]. Also, please take a look at our [formatting guide](https://stackoverflow.com/help/formatting). There's lots of stuff in your question that might benefit from backticks (`\``). — ChrisGPT was on strike, Mar 24 '19 at 01:56
Possible dup of [How to initialize a two-dimensional array in Python?](https://stackoverflow.com/questions/2397141/how-to-initialize-a-two-dimensional-array-in-python) — martineau, Mar 24 '19 at 01:58

Perplexabot · Answer 1 · 2019-03-24T22:58:24.360

This is because

 m = [[0]*n]*n

Makes references of the same object in m. So m[0] is m[1] is ... is m[n-1]. This can be better understood with an example. Suppose you have:

m = [[0] * 3] * 3

print(a)
m[0][0] = 2
print(a)

The output is:

[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
[[2, 0, 0], [2, 0, 0], [2, 0, 0]]

As you can see, changing an element in m[0] changes the same location in m[1] and m[2]. That is because m[1] and m[2] are simply references to m[0].

In the case of

m = [[0 for x in range(n)] for x in range(n)]

You actually create a new list for each location in m. Changing m[0] will not effect m[i] (for 0 < i < n).

Difference between 2 Ways of List Comprehensions in Python?

1 Answers1