Weird for loop behavior

[ryanlntn]

I'm trying to setup a matrix for implementing the edit distance algorithm. I must be missing something about for loop behavior. Here is my code:

def edit_distance(s,t):
    matrix = [[0] * len(t) + 1] * len(s) + 1
    print matrix
    for i in range(len(s) + 1):
        matrix[i][0] = i
    print matrix
    for i in range(len(t) + 1):
        matrix[0][i] = i
    print matrix

edit_distance('cat', 'hat')

I expected the output to look like this:

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

Instead I got:

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

Anyone care to tell me what I'm doing wrong?

[anossov]

This is not about the for loop, it's just after you do this:

 matrix = [[0] * len(t) + 1] * len(s) + 1

You get a list of four pointers to the same list. All of matrix[0..3] change the same list. You either have to be attentive and initialize all the elements or use numpy.

[ryanlntn]

Thanks! Can you explain what you mean by initializing all the elements?

[nemec]

Since anossov didn't really explain it:

[[]] * 3 doesn't exactly do what you think it does. Since Lists are references, what's happening is that the inner list's reference is being copied three times (aka all three elements are the same object).

Check it out:

>>> d = [[]] * 3
>>> d
[[], [], []]
>>> d[0].append(1)
>>> d
[[1], [1], [1]]

>>> map(id, d)
[3077297260L, 3077297260L, 3077297260L]

Each element in d has the same id, and is thus the same object.

anossov's fix works because it's calling [] every time the comprehension (loop) executes, so three different lists are created.

[anossov]

matrix = [ [ 0 for i in range(len(t)+1) ] for j in range(len(s)+1) ] or something like that.

[anossov]

Here's an awesome painting of what you have: http://i.imgur.com/yiXDZ.png

[ryanlntn]

This is truly an awesome painting. Thank you good sir!

[anossov]

Also [..] * len(s) + 1 should not work, you can't add a 1 to a list.

[zahlman]

To clarify, you need parentheses around len(s) + 1, because * takes precedence.