CODEWITHSUNDEEP
pythonarraysnumpy
abdelgha4
abdelgha4

Reputation: 431

How to make nested list behave like numpy array?

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 ?

Upvotes: 1

Views: 198

Answers (1)

abdelgha4
abdelgha4

Reputation: 431

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.

Upvotes: 1

Related Questions