Nested structures

Nested structures#

Introduction#

The idea of this course is to give you an idea of how to construct a nested data structure. As a bonus, we can discuss memory references and copies along the way.

Overview#

Let’s first see how to deal with lists of lists. Consider the following one:

m = [
    ["a", "b"],
    ["c", "d"],
    ["a", "e"],
]

Going back to the example, in practice we have a big external list:

m = [


]

and each of its elements is another list which represents a row:

m = [
        ['a','b'],
        ['c','d'],
        ['a','e']
    ]

So, to access the whole first row ['a','b'], we would simply access the element at index 0 of the external list m:

m[0]

['a', 'b']

To access the first element 'a' of the first row ['a','b'] we would add another subscript operator with index 0:

m[0][0]

'a'

To access the second element 'b' of the first row ['a','b'] we would use instead index 1 :

m[0][1]

'b'

Visiting with style#

Suppose we want to visit all the elements of such a nested structure, and print them one by one.

If you want to keep track of the coordinates where you are in the traversal, you can use a nested for in range like so:

m = [
    ["a", "b"],
    ["c", "d", "e", "f"],
    ["g", "h", "i"],
    ["j"],
]

for i in range(len(m)):
    for j in range(len(m[i])):
        print("i:", i, " j:", j, " m[i][j]:", m[i][j])
    print("ROW END!")

i: 0  j: 0  m[i][j]: a
i: 0  j: 1  m[i][j]: b
ROW END!
i: 1  j: 0  m[i][j]: c
i: 1  j: 1  m[i][j]: d
i: 1  j: 2  m[i][j]: e
i: 1  j: 3  m[i][j]: f
ROW END!
i: 2  j: 0  m[i][j]: g
i: 2  j: 1  m[i][j]: h
i: 2  j: 2  m[i][j]: i
ROW END!
i: 3  j: 0  m[i][j]: j
ROW END!

The algorithm is pretty simple, yet a couple of things are worth noting:

  • we used i as integer index for the rows

  • we used j as integer index for the columns

It follows the convention in maths and Python of naming index variables as i, j, k at nested levels 1, 2, and 3, respectively.

Note

You might wonder, what if I have 4 nested fors? Then, don’t look for a variable name for your index, it’s time to refactor your code, because you should never arrive to that level of nesting! In that case, you could for instance define a separate function to deal with either the inner or outer fors.

Question

Look at the following code that prints again all the elements of m.

Is this good style or not? Why?

for row in m:
    for cell in row:
        print(cell)
    print("ROW END!")

a
b
ROW END!
c
d
e
f
ROW END!
g
h
i
ROW END!
j
ROW END!

Answer

The above style is perfectly fine. Since we don’t explicitly need the position, if we want we can skip holding integer indices i and j and directly obtain pointers to the internal lists, provided we choose proper names for them, like in this case with the row and cell variables.

Extracting rows and columns#

How to extract a row#

One of the first things you might want to do is to extract the i-th row. If you’re implementing a function that does this, you have basically two choices. Either:

  1. return a pointer to the original row

  2. return a copy of the row.

Since a copy consumes memory, why should you ever want to return a copy? Sometimes you just don’t know which use will be done of the data structure. For example, suppose you got a book of exercises which has empty spaces to write exercises in. It’s such a great book everybody in the classroom wants to read it - but you are afraid if the book starts changing hands some careless guy might write on it. To avoid problems, you make a copy of the book and distribute it.

Extracting row pointers#

So first let’s see what happens when you just return a pointer to the original row.

%%tutor

def extrowp(mat, i):
    """ RETURN the ith row from mat        
    """
    return mat[i]

    
m = [
      ['a','b'],
      ['c','d'],
      ['a','e'],    
]

row = extrowp(m, 0)

Extract row with a for#

✪ Now try to implement a version which returns a copy of the row.

Quesstion

You might be tempted to implement something like this - but it wouldn’t work. Why?

%%tutor

def extrow_wrong(mat, i):
    """ RETURN the ith row from mat, as a NEW list"""
    
    row = []
    row.append(mat[i])  
    return row

m = [
      ['a','b'],
      ['c','d'],
      ['a','e'],    
]

row = extrow_wrong(m,0)

Answer

The code above adds a list as element to another empty list. In other words, it is wrapping the row (which is already a list) into another list. If you check the problem in Python Tutor, you will see an arrow going from row to a list of one element which will contain exactly one arrow to the original row.

You can build an actual copy in several ways, with a for, a slice or a list comprehension. Try to implement all versions, starting with the for here. Be sure to check your result with %%tutor. If you run the code with Python Tutor, you should only see one arrow going to the original ['a','b'] row in m, and there should be another ['a','b'] copy somewhere, with row variable pointing to it.

✪ EXERCISE: Implement the function extrowf which RETURNS the i-th row from mat as a NEW list.

  • NOTE: To create a new list use a for cycle which iterates over the elements, not the indices (so don’t use range!)

Hide code cell source 
def extrowf(mat, i):
    row = []
    for x in mat[i]:
        row.append(x)
    return row

# %%tutor

m = [
    ["a", "b"],
    ["c", "d"],
    ["a", "e"],
]

assert extrowf(m, 0) == ["a", "b"]
assert extrowf(m, 1) == ["c", "d"]
assert extrowf(m, 2) == ["a", "e"]

# check it didn't change the original matrix !
r = extrowf(m, 0)
r[0] = "z"
assert m[0][0] == "a"

Extract row with range#

Let’s first quickly see range(n). Maybe you think it should return a sequence of integers, from zero to n - 1. Is it really like this?

range(5)

range(0, 5)

Maybe you expected something like a list [0,1,2,3,4], instead we discovered that Python is quite lazy here: as a matter of fact, range(n) returns an iterable object, which is not a real sequence materialized in memory.

To take a real integer list, we must explicitly ask this iterable object to give us the objects one by one.

When you write for i in range(s) the for loop is doing exactly this, at each round it asks the object range to generate a number from the sequence. If we want the whole sequence materialized in memory, we can generate it by converting the range into a list object:

list(range(5))

[0, 1, 2, 3, 4]

Be careful, though. According to the sequence dimension, this might be dangerous. A billion elements list might saturate your computer RAM.

✪ EXERCISE: Now implement the extrowr iterating over a range of row indices:

  • NOTE 1: To create a new list use a for loop

  • NOTE 2: remember to use a new name for the column index!

Hide code cell source 
def extrowr(mat, i):
    """ RETURN the ith row from mat as a NEW list
    """
    row = []
    for j in range(len(mat[i])):
        row.append(mat[i][j]) 
    return row

# %%tutor

m = [
      ['a','b'],
      ['c','d'],
      ['a','e'],    
]

assert extrowr(m, 0) == ['a','b']
assert extrowr(m, 1) == ['c','d']
assert extrowr(m, 2) == ['a','e']

# check it didn't change the original matrix !
r = extrowr(m, 0)
r[0] = 'z'
assert m[0][0] == 'a'

Extract row with a slice#

✪ Remember slices return a copy of a list? Now try using them.

Implement extrows, which RETURN the i-th row from mat as a NEW list.

  • NOTE: To create it, use slices

Hide code cell source 
def extrows(mat, i):
    return mat[i][:]  # if you omit start end end indexes, you get a copy of the whole list

# %%tutor

m = [
    ["a", "b"],
    ["c", "d"],
    ["a", "e"],
]


assert extrows(m, 0) == ["a", "b"]
assert extrows(m, 1) == ["c", "d"]
assert extrows(m, 2) == ["a", "e"]

# check it didn't change the original matrix !
r = extrows(m, 0)
r[0] = "z"
assert m[0][0] == "a"

Extract row with list comprehension#

✪ Implement extrowc, which RETURNs the i-th row from mat as a NEW list, using a list comprehension.

Hide code cell source 
def extrowc(mat, i):
    return [x for x in mat[i]]

# %%tutor

m = [
    ["a", "b"],
    ["c", "d"],
    ["a", "e"],
]

assert extrowc(m, 0) == ["a", "b"]
assert extrowc(m, 1) == ["c", "d"]
assert extrowc(m, 2) == ["a", "e"]

# check it didn't change the original matrix !
r = extrowc(m, 0)
r[0] = "z"
assert m[0][0] == "a"

Creating new matrices#

Here we’ll focus on lists of lists that have a rectangular shape, meaning all rows have the same number of elements. As these can be interpreted as matrices, we’ll refer to them as such.

Matrices with default values#

✪✪ There are several ways to create a new empty n x m matrix as lists of lists which contains zeros.

Implement empty_matrix, which returns a new n x m matrix as a list of lists filled with zeroes

  • use two nested for cycles:

Hide code cell source 
def empty_matrix(n, m):
    ret = []
    for i in range(n):
        row = []
        ret.append(row)
        for j in range(m):
            row.append(0)
    return ret

assert empty_matrix(1, 1) == [[0]]

assert empty_matrix(1, 2) == [[0, 0]]

assert empty_matrix(2, 1) == [[0], [0]]

assert empty_matrix(2, 2) == [
    [0, 0],
    [0, 0],
]

assert empty_matrix(3, 3) == [
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 0],
]

empty_matrix the elegant way#

To create a new list of 3 elements filled with zeros, you can write like this:

[0] * 3

[0, 0, 0]

The * is kind of multiplying the elements in a list

Given the above, to create a 5x3 matrix filled with zeros, which is a list of seemingly equal lists, you might then be tempted to write like this:

# WRONG
[[0] * 3] * 5

[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]

Why is that (possibly) wrong? Let’s try to inspect it in Python Tutor:

%%tutor
bad = [[0] * 3] * 5

If you look closely, you will see many arrows pointing to the same list of 3 zeros. This means that if we change one number, we will apparently change 5 of them in the whole column !

The right way to create a matrix as list of lists with zeroes is the following:

# CORRECT
[[0] * 3 for i in range(5)]

[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]

EXERCISE: Try creating a matrix with 7 rows and 4 columns and fill it with 5.

Hide code cell source 
lst = [[5] * 4 for i in range(7)]
lst

[[5, 5, 5, 5],
 [5, 5, 5, 5],
 [5, 5, 5, 5],
 [5, 5, 5, 5],
 [5, 5, 5, 5],
 [5, 5, 5, 5],
 [5, 5, 5, 5]]

deep_clone#

✪✪ Let’s try to produce a complete clone of the matrix, also called a deep clone, by creating a copy of the external list and also the internal lists representing the rows.

Question

You might be tempted to write code like this, but it will not work. Why?

%%tutor

# WARNING: WRONG CODE
def deep_clone_wrong(mat):
    """RETURN a NEW list of lists which is a COMPLETE DEEP clone
    of mat (which is a list of lists)
    """
    return mat[:]


m = [
    ["a", "b"],
    ["b", "d"],
]

res = deep_clone_wrong(m)

Answer

return mat[:] is not sufficient, because it’s a SHALLOW clone, and only copies the external list and not also the internal ones ! Note you will have rows in the res list which goes to the original matrix. We don’t want this!

To fix the above code, you will need to iterate through the rows and for each row create a copy of that row.

✪✪ EXERCISE: Implement deep_clone, which RETURNS a NEW list as a complete DEEP CLONE of mat (which is a list of lists)

NOTE: the exercise can be solved very quickly by using the function deepcopy but we invite you to solve it without for now.

Hide code cell source 
def deep_clone(mat):
    ret = []
    for row in mat:
        ret.append(row[:])
    return ret

m = [
    ["a", "b"],
    ["b", "d"],
]

res = [
    ["a", "b"],
    ["b", "d"],
]

# verify the copy
c = deep_clone(m)
assert c == res

# verify it is a DEEP copy (that is, it created also clones of the rows!)
c[0][0] = "z"
assert m[0][0] == "a"

Modifying matrices#

fillc#

✪✪ Implement the function fillc which takes as input mat (a list of lists with dimension nrows x ncol) and MODIFIES it by placing the character c inside all the matrix cells.

  • to visit the matrix use for in range cycles

Ingredients:

  • find matrix dimension

  • two nested fors

  • use range

Hide code cell source 
def fillc(mat, c):
    nrows = len(mat)
    ncols = len(mat[0])

    for i in range(nrows):
        for j in range(ncols):
            mat[i][j] = c

m1 = [["a"]]
m2 = [["z"]]
fillc(m1, "z")
assert m1 == m2

m3 = [["a"]]
m4 = [["y"]]
fillc(m3, "y")
assert m3 == m4

m5 = [["a", "b"]]
m6 = [["z", "z"]]
fillc(m5, "z")
assert m5 == m6

m7 = [
    ["a", "b", "c"],
    ["d", "e", "f"],
    ["g", "h", "i"],
]

m8 = [
    ["y", "y", "y"],
    ["y", "y", "y"],
    ["y", "y", "y"],
]
fillc(m7, "y")
assert m7 == m8

# j   0    1
m9 = [
    ["a", "b"],  # 0
    ["c", "d"],  # 1
    ["e", "f"]   # 2
]

m10 = [
    ["x", "x"],  # 0
    ["x", "x"],  # 1
    ["x", "x"],  # 2
]
fillc(m9, "x")
assert m9 == m10

fillx#

✪✪ Takes a matrix mat as list of lists and a column index j, and MODIFIES mat by placing the 'x' character in all cells of the j-th column.

Hide code cell source 
def fillx(mat, j):
    for row in mat:
        row[j] = "x"

m1 = [["a"]]
fillx(m1, 0)
assert m1 == [["x"]]

m2 = [
    ["a", "b"],
    ["c", "d"],
    ["e", "f"],
]
fillx(m2, 0)
assert m2 == [
    ["x", "b"],
    ["x", "d"],
    ["x", "f"],
]

m3 = [
    ["a", "b"],
    ["c", "d"],
    ["e", "f"],
]
fillx(m3, 1)
assert m3 == [
    ["a", "x"],
    ["c", "x"],
    ["e", "x"],
]

m4 = [
    ["a", "b", "c", "d"],
    ["e", "f", "g", "h"],
    ["i", "l", "m", "n"],
]
fillx(m4, 2)
assert m4 == [
    ["a", "b", "x", "d"],
    ["e", "f", "x", "h"],
    ["i", "l", "x", "n"],
]

fillz#

✪✪ Takes a matrix mat as list of lists and a row index i, and MODIFIES mat by placing the character 'z' in all the cells of the i-th row.

Hide code cell source 
def fillz(mat, i):
    ncol = len(mat[0])
    for j in range(ncol):
        mat[i][j] = "z"

m1 = [["a"]]
fillz(m1, 0)
assert m1 == [["z"]]

m2 = [
    ["a", "b"],
    ["c", "d"],
    ["e", "f"],
]
fillz(m2, 0)
assert m2 == [
    ["z", "z"],
    ["c", "d"],
    ["e", "f"],
]

m3 = [
    ["a", "b"],
    ["c", "d"],
    ["e", "f"],
]
fillz(m3, 1)
assert m3 == [
    ["a", "b"],
    ["z", "z"],
    ["e", "f"],
]

m4 = [
    ["a", "b"],
    ["c", "d"],
    ["e", "f"],
]
fillz(m4, 2)
assert m4 == [
    ["a", "b"],
    ["c", "d"],
    ["z", "z"],
]

stitch_down#

✪✪ Given matrices mat1 and mat2 as list of lists, with mat1 of size u x n and mat2 of size d x n, RETURN a NEW matrix of size (u+d) x n as list of lists, by stitching second mat to the bottom of mat1

  • NOTE: by NEW matrix we intend a matrix with no pointers to original rows (see previous deep clone exercise)

  • for examples, see asserts

Hide code cell source 
def stitch_down(mat1, mat2):
    res = []
    for row in mat1:
        res.append(row[:])
    for row in mat2:
        res.append(row[:])
    return res

m1 = [["a"]]
m2 = [["b"]]
assert stitch_down(m1, m2) == [["a"], ["b"]]

# check we are giving back a deep clone
s = stitch_down(m1, m2)
s[0][0] = "z"
assert m1[0][0] == "a"

m1 = [
    ["a", "b", "c"],
    ["d", "b", "a"],
]
m2 = [
    ["f", "b", "h"],
    ["g", "h", "w"],
]
assert stitch_down(m1, m2) == [
    ["a", "b", "c"],
    ["d", "b", "a"],
    ["f", "b", "h"],
    ["g", "h", "w"],
]

stitch_right#

✪✪✪ Given matrices mata and matb as list of lists, with mata of size n x l and matb of size n x r, RETURN a NEW matrix of size n x (l + r) as list of lists, by stitching second matb to the right end of mata

Hide code cell source 
def stitch_right(mata,matb):    
    ret = []
    for i in range(len(mata)):
        row_to_add =  mata[i][:]
        row_to_add.extend(matb[i])
        ret.append(row_to_add)
    return ret

ma1 = [
    ["a", "b", "c"],
    ["d", "b", "a"],
]
mb1 = [
    ["f", "b"],
    ["g", "h"],
]

assert stitch_right(ma1, mb1) == [
    ["a", "b", "c", "f", "b"],
    ["d", "b", "a", "g", "h"],
]

insercol#

✪✪ Given a matrix mat as list of lists, a column index j and a list new_col, write a function insercol(mat,j,new_col) which MODIFIES mat inserting the new column at position j.

Example - given:

m  = [
        [5,4,6],   
        [4,7,1],   
        [3,2,6],  
]

By calling


>>> insercol(m, 2, [7,9,3])

m will be MODIFIED with the insertion of column [7,9,3] at position j=2

>>> m
[
        [5,4,7,6],   
        [4,7,9,1],   
        [3,2,3,6],  
]

  • for other examples, see asserts

  • HINT: lists already have a handy method .insert, so there is isn’t much code to write, just write the right one ;-)

Hide code cell source 
def insercol(mat, j, nuova_col):
    for i in range(len(mat)):
        mat[i].insert(j, nuova_col[i])

m1 = [[5]]
assert insercol(m1, 1, [8]) is None  # the function shouldn't return anything!
assert m1 == [[5, 8]]

m2 = [[5]]
insercol(m2, 0, [8])
assert m2 == [[8, 5]]

m3 = [
    [5, 4, 2],
    [8, 9, 3],
]
insercol(m3, 1, [7, 6])
assert m3 == [
    [5, 7, 4, 2],
    [8, 6, 9, 3],
]


m4 = [
    [5, 4, 6],
    [4, 7, 1],
    [3, 2, 6],
]
insercol(m4, 2, [7, 9, 3])

assert m4 == [
    [5, 4, 7, 6],
    [4, 7, 9, 1],
    [3, 2, 3, 6],
]

threshold#

✪✪ Takes a matrix as a list of lists (every list has the same dimension) and RETURN a NEW matrix as list of lists where there is True if the corresponding input element is greater than t, otherwise return False

Ingredients:

  • a variable for the matrix to return

  • for each original row, we need to create a new list

Hide code cell source 
def threshold(mat, t):
    ret = []
    for row in mat:
        new_row = []
        ret.append(new_row)
        for el in row:
            new_row.append(el > t)
    return ret

morig = [
    [1, 4, 2],
    [7, 9, 3],
]

m1 = [
    [1, 4, 2],
    [7, 9, 3],
]

r1 = [
    [False, False, False],
    [True, True, False],
]
assert threshold(m1, 4) == r1
assert m1 == morig  # verify original didn't change

m2 = [
    [5, 2],
    [3, 7],
]

r2 = [
    [True, False],
    [False, True],
]
assert threshold(m2, 4) == r2

swap_rows#

✪✪ We will try swapping a couple of rows of a matrix

There are several ways to proceed. Before continuing, make sure to know how to exchange two values by solving this simple exercise - check your result in Python Tutor

x = 3
y = 7

# write here the code to swap x and y (do not directly use the constants 3 and 7!)
Hide code cell source 
k = x
x = y
y = k

✪✪ Takes a matrix mat as list of lists, and RETURN a NEW matrix where rows at indexes i1 and i2 are swapped

Hide code cell source 
def swap_rows(mat, i1, i2):
    # deep clones
    ret = []
    for row in mat:
        ret.append(row[:])
    #swaps
    s = ret[i1]
    ret[i1] = ret[i2]
    ret[i2] = s
    return ret

m1 = [
    ["a", "d"],
    ["b", "e"],
    ["c", "f"],
]

r1 = swap_rows(m1, 0, 2)
assert r1 == [
    ["c", "f"],
    ["b", "e"],
    ["a", "d"],
]

r1[0][0] = "z"
assert m1[0][0] == "a"

m2 = [
    ["a", "d"],
    ["b", "e"],
    ["c", "f"],
]

# swap with itself should in fact generate a deep clone
r2 = swap_rows(m2, 0, 0)
assert r2 == [
    ["a", "d"],
    ["b", "e"],
    ["c", "f"],
]

r2[0][0] = "z"
assert m2[0][0] == "a"

swap_cols#

✪✪ Takes a matrix mat and two column indices j1 and j2 and RETURN a NEW matrix where the columns j1 and j2 are swapped

Hide code cell source 
def swap_cols(mat, j1, j2):
    ret = []
    for row in mat:
        new_row = row[:]
        new_row[j1] = row[j2]
        new_row[j2] = row[j1]
        ret.append(new_row)
    return ret

m1 = [
    ["a", "b", "c"],
    ["d", "e", "f"],
]

r1 = swap_cols(m1, 0, 2)

assert r1 == [
    ["c", "b", "a"],
    ["f", "e", "d"],
]

r1[0][0] = "z"
assert m1[0][0] == "a"

Transpose#

Let’s see how to transpose a matrix in-place. The transpose \(M^T\) of a matrix \(M\) is defined as

\(M^T[i][j] = M[j][i]\)

The definition is simple yet implementation might be tricky. If you’re not careful, you could easily end up swapping the values twice and get the same original matrix. To prevent this, iterate only the upper triangular part of the matrix and remember range function can also have a start index:

list(range(3, 7))

[3, 4, 5, 6]

✪✪✪ EXERCISE If you read all the above, you can now proceed implementing the transpose_1 function, which MODIFIES the given nxn matrix mat by transposing it in-place.

  • If the matrix is not nxn, raises a ValueError

Hide code cell source 
def transpose(mat):
    if len(mat) != len(mat[0]):
        raise ValueError(
            "Matrix should be nxn, found instead %s x %s" % (len(mat), len(mat[0]))
        )
    for i in range(len(mat)):
        for j in range(i + 1, len(mat[i])):
            el = mat[i][j]
            mat[i][j] = mat[j][i]
            mat[j][i] = el

# let's try wrong matrix dimensions:
try:
    transpose([[3, 5]])
    raise Exception("SHOULD HAVE FAILED !")
except ValueError:
    pass

m1 = [["a"]]

transpose(m1)
assert m1 == [["a"]]

m2 = [
    ["a", "b"],
    ["c", "d"],
]

transpose(m2)
assert m2 == [
    ["a", "c"],
    ["b", "d"],
]