EvgeniySharapov - 5 months ago 17

Python Question

I have written Longest Common SubSequence in Python using recursion with memoization:

`def print2d(table):`

print '\n'.join([''.join(['{:4}'.format(item) for item in row]) for row in table])

a="123"

b="213"

m = [[-1]*len(b)]*len(a)

def lcs(i,j):

print i, j

print2d(m)

if i== -1 or j == -1:

return 0;

if m[i][j] != -1:

return m[i][j]

res = 0

res = max(res, lcs(i, j-1))

res = max(res, lcs(i-1, j))

if a[i] == b[j]:

res = max(res, 1 + lcs(i-1,j-1))

m[i][j]=res

return res

print lcs(len(a)-1,len(b)-1)

print2d(m)

All those

`print`

`0 -1`

-1 -1 -1

-1 -1 -1

-1 -1 -1

-1 0

-1 -1 -1

-1 -1 -1

-1 -1 -1

0 -1

0 -1 -1

0 -1 -1

0 -1 -1

1 1

1 -1 -1

1 -1 -1

1 -1 -1

1 0

1 -1 -1

1 -1 -1

1 -1 -1

0 1

1 -1 -1

1 -1 -1

1 -1 -1

Why all of a sudden on the step

`0 -1`

So, I quickly created C++ program doing exactly the same thing the same way:

`#include <iostream>`

#include <iomanip>

#include <string>

#include <cstring>

using namespace std;

string a = "123",

b = "213";

int mem[1000][1000];

int lcs(int i, int j) {

cout << i << " " << j << "\n";

for(auto i = 0; i < a.length(); i++){

for(auto j = 0; j < b.length(); j++){

cout << setw(4) << right << mem[i][j];

}

cout << "\n";

}

if (i == -1 || j == -1) {

return 0;

}

if (mem[i][j] != -1) {

return mem[i][j];

}

int res = 0;

res = max(res, lcs(i, j - 1));

res = max(res, lcs(i - 1, j));

if (a[i] == b[j]) {

res = max(res, 1 + lcs(i - 1, j - 1));

}

mem[i][j] = res;

return res;

}

int main(){

memset(mem, -1, sizeof mem );

int r = lcs(a.length()-1, b.length()-1);

cout << r << "\n";

return 0;

}

And it works as expected. Corresponding tables look like this:

`0 -1`

-1 -1 -1

-1 -1 -1

-1 -1 -1

-1 0

-1 -1 -1

-1 -1 -1

-1 -1 -1

0 -1

0 -1 -1

-1 -1 -1

-1 -1 -1

1 1

0 -1 -1

1 -1 -1

1 -1 -1

1 0

0 -1 -1

1 -1 -1

1 -1 -1

0 1

0 -1 -1

1 -1 -1

1 -1 -1

I am puzzled why Python and C++ code that are not that different produce such drastically different results.

Am I missing something about how recursive functions in Python work? Or is it because in Python I use list of lists and not 2D array as in C++?

Answer

The initialization of `m`

is the problem:

```
m = [[-1]*len(b)]*len(a)
```

The final list produced is using a reference to the same list of [-1,...,-1]. So when you modify the list at m[0], you are also modifying the other locations. Something like the following should fix this:

```
m = [[-1 for i in range(len(b))] for j in range(len(a))]
```