1

I am writing a simple dynamic programming algorithm to traverse a matrix in Python. Due to my lack of understanding in Python's scoping rules, I have difficulty fixing this bug.

Here's a part of my code:

# a new null matrix.
footstep = []
for i in range(size):
    row = [0]*size
    footstep.append(row)

def min_val(m, n, footstep):
    # copy a new footstep 2D-matrix.
    fs = list(footstep)

    if ((m == 0) and (n == 0)):
        print "origin"
        return get_grid(0, 0)

    ......
    ......
    ......

    return (min(min_val(m-1, n, fs), min_val(m, n-1, fs)

print min_val(4, 4, footstep)
print footstep

At the start of the function call I copied a new identical footstep list. Therefore, my expectation is that : the footstep list in the global scope must not have changed.

How should I fix my code? Please help.

zoonoo
  • 485
  • 1
  • 6
  • 13

1 Answers1

2

You copied the list by adding all the elements of the old list to it. Therefore, while the list itself is new, the elements in it still point to the same objects.

To fix this, individually create a copy of each object in your array during copy instead.

EXAMPLE (pseudocode):

Where you do this

footstep = []
for i in range(size):
    row = [0]*size
    footstep.append(row)

You need to do something like

for each element in the old array
  create a copy of the old element
  you may need to implement some copy() method which makes a copy of your object
  add the copy to the new array

Also see this link for more explanation of shallow vs deep copy: What is the difference between a deep copy and a shallow copy?

What you do is a shallow copy, what you need is called a deep copy.

Community
  • 1
  • 1
nhouser9
  • 6,730
  • 3
  • 21
  • 42
  • 1
    @idjaw i know nothing about python, so my example will be in pseudocode, but i will edit my answer. – nhouser9 Apr 16 '16 at 17:15