How to make nested list behave like numpy array?

Question

I'm trying to implements an algorithm to count subsets with given sum in python which is

import numpy as np 
  
maxN = 20
maxSum = 1000
minSum = 1000
base = 1000
dp = np.zeros((maxN, maxSum + minSum))
v = np.zeros((maxN, maxSum + minSum)) 
# Function to return the required count  
def findCnt(arr, i, required_sum, n) : 
    # Base case  
    if (i == n) : 
        if (required_sum == 0) : 
            return 1
        else : 
            return 0
    # If the state has been solved before  
    # return the value of the state  
    if (v[i][required_sum + base]) : 
        return dp[i][required_sum + base]
    # Setting the state as solved  
    v[i][required_sum + base] = 1
    # Recurrence relation  
    dp[i][required_sum + base] = findCnt(arr, i + 1, required_sum, n) + findCnt(arr, i + 1, required_sum - arr[i], n)
    return dp[i][required_sum + base]
  
arr = [ 2, 2, 2, 4 ]  
n = len(arr) 
k = 4
  
print(findCnt(arr, 0, k, n))

And it gives the expected result, but I was asked to not use numpy, so I replaced numpy arrays with nested lists like this :

#dp = np.zeros((maxN, maxSum + minSum)) replaced by
dp = [[0]*(maxSum + minSum)]*maxN
#v = np.zeros((maxN, maxSum + minSum)) replaced by
v = [[0]*(maxSum + minSum)]*maxN

but now the program always gives me 0 in the output, I think this is because of some behavior differences between numpy arrays and nested lists, but I don't know how to fix it

EDIT :

thanks to @venky__ who provided this solution in the comments :

[[0 for i in range( maxSum + minSum)] for i in range(maxN)]

and it worked, but I still don't understand what is the difference between it and what I was doing before, I tried :

print( [[0 for i in range( maxSum + minSum)] for i in range(maxN)] == [[0]*(maxSum + minSum)]*maxN )

And the result is True, so how this was able to fix the problem ?

`[[0 for i in range( maxSum + minSum)] for i in range(maxN)]` — Equinox, Nov 07 '20 at 13:53
@venky__ thank you soo much this has solved the problem, but what is the difference between it and `[[0]*(maxSum + minSum)]*maxN` ? — abdelgha4, Nov 07 '20 at 13:56
read the first comment of the accepted answer. https://stackoverflow.com/questions/5205575/how-do-i-get-an-empty-array-of-any-size-in-python — Equinox, Nov 07 '20 at 14:27

score 1 · Accepted Answer · answered Nov 07 '20 at 14:36

1

It turns out that I was using nested lists the wrong way to represent 2d arrays, since python was not crating separate objets, but the same sub list indexes was referring to the same integer object, for better explanation please read this.

answered Nov 07 '20 at 14:36

abdelgha4

351
1
16

Thanks for the link, the link was helpful! – dcxst Apr 28 '22 at 12:15

How to make nested list behave like numpy array?

1 Answers1