Python: Different methods to initialize 2D arrays gives different outputs

Question

I was solving a few questions involving dynamic programming. I initialized the dp table as -

n = 3
dp = [[False]*n]*n
print(dp)

#Output - [[False, False, False], [False, False, False], [False, False, False]]

Followed by which I set the diagonal elements to True using -

for i in range(n):
    dp[i][i] = True

print(dp)

#Output - [[True, True, True], [True, True, True], [True, True, True]]

However, the above sets every value in dp to True. But when I initialize dp as -

dp = [[False]*n for i in range(n)]

Followed by setting diagonal elements to True, I get the correct output - [[True, False, False], [False, True, False], [False, False, True]]

So how exactly does the star operator generate values of the list?

score 5 · Accepted Answer · answered Jul 05 '20 at 12:21

When you do dp = [[False]*n]*n, you get a list of n of the same lists, as in, when you modify one, all are modified. That's why with that loop of n, you seemingly modify all n^2 elements.

You can check it like this:

[id(x) for x in dp]
> [1566380391432, 1566380391432, 1566380391432, 1566380391432, 1566380391432] # you'll see same values

With dp = [[False]*n for i in range(n)] you are creating different lists n times. Let's try again for this dp:

 [id(x) for x in dp]
 [1566381807176, 1566381801160, 1566381795912, 1566381492552, 1566380166600]

In general, opt to use * to expand immutable data types, and use for ... to expand mutable data types (like lists).

Took me long enough but I guessed it right haha!! Nice answer +1. — Agent_Orange, Jul 05 '20 at 12:23

score 0 · Answer 2 · answered Jul 05 '20 at 12:23

Your issue is that in the first example, you are not actually creating more lists.

To explain, lets go threw the example line by line.

First, you create a new list [False]*3. This will create list with the value False 3 times.

Next, you create a different list with a reference to the first list. Note that the first list is not copied, only a reference is stored.

Next, by multiplying by 3 you create a list with 3 references to the same list. Since these are only references, changing one will change the others too.

This is why assigning dp[i][i]=True, you are actually setting all element i of all three lists to True, since they are all 3 the same list. Thus if you do this for all i all value in all (but there is only one) lists will be set to true.

The second option actually creates 3 separate lists, so the code works properly.

Python: Different methods to initialize 2D arrays gives different outputs

2 Answers2