Matrices: list of lists¶
Introduction¶
Python natively does not provide easy and efficient ways to manipulate matrices. To do so, you would need an external library called numpy which will be seen later in the course. For now we will limit ourselves to using matrices as lists of lists because
There are a couple of ways in Python to represent matrices: as lists of lists, or with the external library Numpy. The most used is surely Numpy but we see both representations anyway. Let’s see the reason and main differences:
Lists of lists  as in this notebook:
native in Python
not efficient
lists are pervasive in Python, you will probably encounter matrices expressed as lists of lists anyway
you get an idea of how to construct a nested data structure
we can discuss memory referencies and copies along the way
Numpy  see other tutorial Numpy matrices 1. not natively available in Python 1. efficient 1. used by many scientific libraries (scipy, pandas) 1. the syntax to access elements is slightly different from lists of lists 1. in rare cases it might bring installation problems and/or conflicts (implementation is not pure Python)
What to do¶
unzip exercises in a folder, you should get something like this:
matrixlists
matrixlist.ipynb
matrixlistsol.ipynb
jupman.py
WARNING: to correctly visualize the notebook, it MUST be in an unzipped folder !
open Jupyter Notebook from that folder. Two things should open, first a console and then browser. The browser should show a file list: navigate the list and open the notebook
matriceslists/matriceslists.ipynb
Go on reading that notebook, and follow instuctions inside.
Shortcut keys:
to execute Python code inside a Jupyter cell, press
Control + Enter
to execute Python code inside a Jupyter cell AND select next cell, press
Shift + Enter
to execute Python code inside a Jupyter cell AND a create a new cell aftwerwards, press
Alt + Enter
If the notebooks look stuck, try to select
Kernel > Restart
Overview¶
So let’s see these lists of lists.For example, we can consider the following a matrix with 3 rows and 2 columns, or in short 3x2 matrix:
[2]:
m = [
['a','b'],
['c','d'],
['a','e']
]
For convenience, we assume as input to our functions there won’t be matrices with no rows, nor rows with no columns.
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
:
[3]:
m[0]
[3]:
['a', 'b']
To access the second whole second row ['c','d']
, we would access the element at index 1 of the external list m
:
[4]:
m[1]
[4]:
['c', 'd']
To access the second whole third row ['c','d']
, we would access the element at index 2 of the external list m
:
[5]:
m[2]
[5]:
['a', 'e']
To access the first element 'a'
of the first row ['a','b']
we would add another subscript operator with index 0:
[6]:
m[0][0]
[6]:
'a'
To access the second elemnt 'b'
of the first row ['a','b']
we would use instead index 1 :
[7]:
m[0][1]
[7]:
'b'
WARNING: When a matrix is a list of lists, you can only access values with notation m[i][j]
, NOT with m[i,j]
!!
[8]:
# write here the wrong notation m[0,0] and see which error you get:
Exercises¶
Now implement the following functions.
REMEMBER: if the cell is executed and nothing happens, it is because all the assert tests have worked! In such case you probably wrote correct code but careful, these kind of tests are never exhaustive so you could have still made some error.
III COMMANDMENT: You shall never reassign function parameters
Do not perform any of these assignments, as you risk losing the parameter passed during function call:
[9]:
def disgrace(my_list):
my_list = [666] # you lost the [1,2,3] passed from external call!
print(my_list) # prints 666
x = [1,2,3]
disgrace(x)
[666]
For the only case when you have composite parameters like lists or dictionaries, you can write like below IF AND ONLY IF the function description requires to MODIFY the internal elements of the parameter (like for example sorting a list inplace or changing the field of a dictionary.
[10]:
# MODIFY my_list in some way
def allowed(my_list):
my_list[2] = 9
outside = [8,5,7]
allowed(outside)
print(outside)
[8, 5, 9]
VI COMMANDMENT You shall use return
command only if you see written RETURN in the function description!
If there is no return
in function description, the function is intended to return None
. In this case you don’t even need to write return None
, as Python will do it implicitly for you.
If the function requires to RETURN a NEW object, you shall not fall into the temptation of modifying the input:
[11]:
# RETURN a NEW sorted list
def pain(my_list):
my_list.sort() # BAD, you are modifying the input list instead of creating a new one!
return my_list
[12]:
# RETURN a NEW list
def crisis(my_list):
my_list[0] = 5 # BAD, as above
return my_list
Matrix dimensions¶
✪ EXERCISE: For getting matrix dimensions, we can use normal list operations. Which ones? You can assume the matrix is well formed (all rows have equal length) and has at least one row and at least one column
[13]:
m = [
['a','b'],
['c','d'],
['a','e']
]
[14]:
# write here code for printing rows and columns
rows
3
columns
2
Extracting rows and columns¶
How to extract a row¶
One of the first things you might want to do is to extract the ith row. If you’re implementing a function that does this, you have basically two choices. Either you
return a pointer to the original row
return a copy of the row.
Since a copy consumes memory, why should you ever want to return a copy? Sometimes you should because you 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 (let’s leave copyright infringment matters aside :)
Extracting row pointers¶
So first let’s see what happens when you just return a pointer to the original row.
NOTE: For convenience, at the end of the cell we put a magic call to jupman.pytut()
which shows the code execution like in Python tutor (for further info about jupman.pytut()
, see here). If you execute all the code in Python tutor, you will see that at the end you have two arrow pointers to the row ['a','b']
, one starting from m
list and one from row
variable.
[15]:
# WARNING: FOR PYTHON TUTOR TO WORK, REMEMBER TO EXECUTE THIS CELL with Shift+Enter
# (it's sufficient to execute it only once)
import jupman
[16]:
def extrowp(mat, i):
""" RETURN the ith row from mat
"""
return mat[i]
m = [
['a','b'],
['c','d'],
['a','e'],
]
row = extrowp(m, 0)
jupman.pytut()
[16]:
extrowf¶
✪ Now try to implement a version which returns a copy of the row.
QUESTION: You might be tempted to implement something like this  but it wouldn’t work. Why?
[17]:
# WARNING: WRONG CODE!!!!
def extrow_wrong(mat, i):
""" RETURN the ith row from mat.
NOTE: the row MUST be a new list ! """
riga = []
riga.append(mat[i])
return riga
m = [
['a','b'],
['c','d'],
['a','e'],
]
row = extrow_wrong(m,0)
jupman.pytut()
[17]:
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 Python Tutor  to visualize python tutor inside the cell output, you might use the special command jupman.pytut()
at the end of the cell as we did before. 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 esrowf
which RETURNS the i
th row from mat
NOTE: the row MUST be a new list! To create a new list use a for cycle which iterates over the elements, not the indeces (so don’t use range!)
[18]:
def extrowf(mat, i):
""" RETURN the ith row from mat.
"""
raise Exception('TODO IMPLEMENT ME !')
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'
# uncomment to visualize execution here
#jupman.pytut()
Extract row with range¶
Let’s first rapidly see range(n)
. Maybe you think it should return a sequence of integers, from zero to n  1
. Is it really like this?
[19]:
range(5)
[19]:
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:
[20]:
list(range(5))
[20]:
[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 (in 2020 notebooks often have 4 gigabytes of RAM, that is, 4 billion bytes).
✪ EXERCISE: Now implement the extrowr
iterating over a range of row indexes:
NOTE 1: the row MUST be a new list! To create a new list use a
for
loopNOTE 2: remember to use a new name for the column index!
[21]:
def extrowr(mat, i):
""" RETURN the ith row from mat.
"""
raise Exception('TODO IMPLEMENT ME !')
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'
# uncomment to visualize execution here
#jupman.pytut()
Extract row with a slice¶
✪ Remember slices return a copy of a list? Now try to use them.
NOTE: the row MUST be a new list! To create it, use slices.
[22]:
def extrows(mat, i):
""" RETURN the ith row from mat.
"""
raise Exception('TODO IMPLEMENT ME !')
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'
# uncomment to visualize execution here
#jupman.pytut()
Extract row with list comprehension¶
✪ Implement extrowc
, which RETURNs the i
th row from mat
. To create a new list use a list comprehension.
NOTE: the row MUST be a new list!
[23]:
def extrowc(mat, i):
raise Exception('TODO IMPLEMENT ME !')
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'
#jupman.pytut()
Extract column with a for
¶
✪✪ Now try extracting a column at j
th position. This time we will be forced to create a new list, so we don’t have to wonder if we need to return a pointer or a copy.
Implement extcolf
, which RETURN the j
th column from mat
. To create it, use a for
loop.
[24]:
def extcolf(mat, j):
raise Exception('TODO IMPLEMENT ME !')
m = [
['a','b'],
['c','d'],
['a','e'],
]
assert extcolf(m, 0) == ['a','c','a']
assert extcolf(m, 1) == ['b','d','e']
# check returned column does not modify m
c = extcolf(m,0)
c[0] = 'z'
assert m[0][0] == 'a'
#jupman.pytut()
Extract column with a list comprehension¶
✪✪ Implement extcolc
, which RETURNS the j
th column from mat
: to create it, use a list comprehension.
[25]:
def extcolc(mat, j):
raise Exception('TODO IMPLEMENT ME !')
m = [
['a','b'],
['c','d'],
['a','e'],
]
assert extcolc(m, 0) == ['a','c','a']
assert extcolc(m, 1) == ['b','d','e']
# check returned column does not modify m
c = extcolc(m,0)
c[0] = 'z'
assert m[0][0] == 'a'
#jupman.pytut()
Creating new matrices¶
empty matrix¶
✪✪ There are several ways to create a new empty 3x5 matrix as lists of lists which contains zeros.
Implement empty_matrix
, which RETURN a NEW matrix nxn as a list of lists filled with zeroes
use two nested
for
cycles:
[26]:
def empty_matrix(n, m):
raise Exception('TODO IMPLEMENT ME !')
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:
[27]:
[0]*3
[27]:
[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:
[28]:
# WRONG
[[0]*3]*5
[28]:
[[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:
[29]:
bad = [[0]*3]*5
jupman.pytut()
[29]:
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:
[30]:
# CORRECT
[[0]*3 for i in range(5)]
[30]:
[[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.
Show solution[31]:
# write here
[31]:
[[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?
[32]:
# 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)
# Notice you will have arrows in res list going to the _original_ mat. We don't want this !
jupman.pytut()
[32]:
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)
[33]:
def deep_clone(mat):
raise Exception('TODO IMPLEMENT ME !')
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
NOTE: This function returns nothing!
If in the function text it is not mentioned to return values, DO NOT place the return
. If by chance you put it anyway it is not the world’s end, but to avoid confusion is much better having a behaviour consisting with the text.
[34]:
def fillc(mat, c):
raise Exception('TODO IMPLEMENT ME !')
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.
Example:
m = [
['a','b','c','d'],
['e','f','g','h'],
['i','l','m','n']
]
After the call to
fillx(m,2)
the matrix m
will be changed like this:
>>> print(m)
[
['a','b','x','d'],
['e','f','x','h'],
['i','l','x','n']
]
[35]:
def fillx(mat, j):
raise Exception('TODO IMPLEMENT ME !')
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.
Example:
m = [
['a','b'],
['c','d'],
['e','f'],
['g','h']
]
After the call to
fillz(m,2)
the matrix m
will be changed like this:
>>> print(m)
[
['a','b'],
['c','d'],
['z','z'],
['g','h']
]
[36]:
def fillz(mat, i):
raise Exception('TODO IMPLEMENT ME !')
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 assert
[37]:
def stitch_down(mat1, mat2):
raise Exception('TODO IMPLEMENT ME !')
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'] ]
res = [ ['a','b','c'],
['d','b','a'],
['f','b','h'],
['g','h','w'] ]
assert stitch_down(m1, m2) == res
stitch_up¶
✪✪ 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 first mat to the bottom of mat2
NOTE: by NEW matrix we intend a matrix with no pointers to original rows (see previous
deep_clone
exercise)To implement this function, use a call to the method stitch_down you implemented before.
For examples, see assert
[38]:
def stitch_up(mat1, mat2):
raise Exception('TODO IMPLEMENT ME !')
m1 = [ ['a'] ]
m2 = [ ['b'] ]
assert stitch_up(m1, m2) == [ ['b'],
['a'] ]
# check we are giving back a deep clone
s = stitch_up(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'] ]
res = [ ['f','b','h'],
['g','h','w'],
['a','b','c'],
['d','b','a'] ]
assert stitch_up(m1, m2) == res
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
[39]:
def stitch_right(mata,matb):
raise Exception('TODO IMPLEMENT ME !')
ma1 = [ ['a','b','c'],
['d','b','a'] ]
mb1 = [ ['f','b'],
['g','h'] ]
r1 = [ ['a','b','c','f','b'],
['d','b','a','g','h'] ]
assert stitch_right(ma1, mb1) == r1
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
[40]:
def threshold(mat, t):
raise Exception('TODO IMPLEMENT ME !')
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
Show solution[41]:
x = 3
y = 7
# write here the code to swap x and y (do not directly use the constants 3 and 7!)
✪✪ Takes a matrix mat
as list of lists, and RETURN a NEW matrix where rows at indexes i1
and i2
are swapped
[42]:
def swap_rows(mat, i1, i2):
raise Exception('TODO IMPLEMENT ME !')
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 indeces j1
and j2
and RETURN a NEW matrix where the columns j1
and j2
are swapped
[43]:
def swap_cols(mat, j1, j2):
raise Exception('TODO IMPLEMENT ME !')
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'
Other exercises¶
diag¶
diag
extracts the diagonal of a matrix. To do so, diag
requires an nxn matrix as input. To make sure we actually get an nxn matrix, this time you will have to validate the input, that is check if the number of rows is equal to the number of columns (as always we assume the matrix has at least one row and at least one column). If the matrix is not nxn, the function should stop raising an exception. In particular, it shoud raise a
ValueError, which is the standard Python exception to raise when the expected input is not correct and you can’t find any other more specific error.
Just for illustrative puroposes, we show here the index numbers i
and j
and avoid putting apices around strings:
\ j 0,1,2,3
i
[
0 [a,b,c,d],
1 [e,f,g,h],
2 [p,q,r,s],
3 [t,u,v,z]
]
Let’s see a step by step execution:
\ j 0,1,2,3
i
[
extract from row at i=0 > 0 [a,b,c,d], 'a' is extracted from mat[0][0]
1 [e,f,g,h],
2 [p,q,r,s],
3 [t,u,v,z]
]
\ j 0,1,2,3
i
[
0 [a,b,c,d],
extract from row at i=1 > 1 [e,f,g,h], 'f' is extracted from mat[1][1]
2 [p,q,r,s],
3 [t,u,v,z]
]
\ j 0,1,2,3
i
[
0 [a,b,c,d],
1 [e,f,g,h],
extract from row at i=2 > 2 [p,q,r,s], 'r' is extracted from mat[2][2]
3 [t,u,v,z]
]
\ j 0,1,2,3
i
[
0 [a,b,c,d],
1 [e,f,g,h],
2 [p,q,r,s],
extract from row at i=3 > 3 [t,u,v,z] 'z' is extracted from mat[3][3]
]
From the above, we notice we need elements from these indeces:
i, j
1, 1
2, 2
3, 3
There are two ways to solve this exercise, one is to use a double for
(a nested for to be precise) while the other method uses only one for
. Try to solve it in both ways. How many steps do you need with double for? and with only one?
✪✪ EXERCISE: Implement the diag
function, which given an n
xn
matrix mat
as a list of lists, RETURN a list which contains the elemets in the diagonal (top left to bottom right corner).
if
mat
is notn
xn
raiseValueError
[44]:
def diag(mat):
raise Exception('TODO IMPLEMENT ME !')
# TEST START  DO NOT TOUCH!
# if you wrote the whole code correct, and execute the cell, Python shouldn't raise `AssertionError`
m = [ ['a','b','c'],
['d','e','f'],
['g','h','i'] ]
assert diag(m) == ['a','e','i']
try:
diag([ ['a','b'] ]) # 1x2 dimension, not square
raise Exception("SHOULD HAVE FAILED !") # if diag raises an exception which is ValueError as we
# expect it to do, the code should never arrive here
except ValueError: # this only catches ValueError. Other types of errors are not catched
pass # In an except clause you always need to put some code.
# Here we put a placeholder just to fill in
# TEST END
anti_diag¶
✪✪ Given an nxn matrix mat as a list of lists, RETURN a list which contains the elemets in the antidiagonal (top right to bottom left corner).
If mat is not
n
xn
raiseValueError
Before implementing it, be sure to write down understand the required indeces as we did in the example for the diag function.
Show solution[45]:
def anti_diag(mat):
raise Exception('TODO IMPLEMENT ME !')
m = [ ['a','b','c'],
['d','e','f'],
['g','h','i'] ]
assert anti_diag(m) == ['c','e','g']
# If you have doubts about the indexes remember to try it in python tutor !
# jupman.pytut()
is_utriang¶
✪✪✪ You will now try to iterate only the lower triangular half of a matrix. Let’s look at an example:
[46]:
m = [
[3,2,5,8],
[0,6,2,3],
[0,0,4,9],
[0,0,0,5]
]
Just for illustrative puroposes, we show here the index numbers i
and j
:
\ j 0,1,2,3
i
[
0 [3,2,5,8],
1 [0,6,2,3],
2 [0,0,4,9],
3 [0,7,0,5]
]
Let’s see a step by step execution an a nonupper triangular matrix:
\ j 0,1,2,3
i
[
0 [3,2,5,8],
start from row at index i=1 > 1 [0,6,2,3], Check until column limit j=0 included
2 [0,0,4,9],
3 [0,7,0,5]
]
One zero is found, time to check next row.
\ j 0,1,2,3
i
[
0 [3,2,5,8],
1 [0,6,2,3],
check row at index i=2 > 2 [0,0,4,9], Check until column limit j=1 included
3 [0,7,0,5]
]
Two zeros are found. Time to check next row.
\ j 0,1,2,3
i
[
0 [3,2,5,8],
1 [0,6,2,3],
2 [0,0,4,9],
check row at index i=3 > 3 [0,7,0,5] Check until column limit j=2 included
] BUT can stop sooner at j=1 because
number at j=1 is different from zero.
As soon as 7 is found, can return False
In this case the matrix is not upper
triangular
VII COMMANDMENT You shall also write on paper!
When you develop these algorithms, it is fundamental to write down a step by step example like the above to get a clear picture of what is happening. Also, if you write down the indeces correctly, you will easily be able to derive a generalization. To find it, try to further write the found indeces in a table.
For example, from above for each row index i
we can easily find out which limit index j
we need to reach for our hunt for zeros:
i 
limit j (included) 
Notes 

1 
0 
we start from row at index i=1 
2 
1 

3 
2 
From the table, we can see the limit for j can be calculated in terms of the current row index i
with the simple formula i  1
The fact you need to span through rows and columns suggest you need two for
s, one for rows and one for columns  that is, a nested for.
please use ranges of indexes to carry out the task (no
for row in mat
..)please use letter
i
as index for rows,j
as index of columns and in case you need itn
letter as matrix dimension
HINT 1: remember you can set range to start from a specific index, like range(3,7)
will start from 3 and end to 6 included (last 7 is excluded!)
HINT 2: To implement this, it is best looking for numbers different from zero. As soon as you find one, you can stop the function and return False. Only after all the number checking is done you can return True.
Finally, be reminded of the following:
II COMMANDMENT Whenever you introduce a variable with a for
cycle, such variable must be new
If you defined a variable before, you shall not reintroduce it in a for
, since it’s confusing and error prone.
So avoid these sins:
[47]:
i = 7
for i in range(3): # sin, you lose i variable
print(i)
0
1
2
[48]:
def f(i):
for i in range(3): # sin again, you lose i parameter
print(i)
[49]:
for i in range(2):
for i in range(3): # debugging hell, you lose i from outer for
print(i)
0
1
2
0
1
2
✪✪✪ EXERCISE: If you read all the above, start implementing the function is_utriang
, which RETURN True
if the provided n
xn
matrix is upper triangular, that is, has all the entries below the diagonal set to zero. Return False
otherwise.
[50]:
def is_utriang(mat):
raise Exception('TODO IMPLEMENT ME !')
assert is_utriang([ [1] ]) == True
assert is_utriang([ [3,2,5],
[0,6,2],
[0,0,4] ]) == True
assert is_utriang([ [3,2,5],
[0,6,2],
[1,0,4] ]) == False
assert is_utriang([ [3,2,5],
[0,6,2],
[1,1,4] ]) == False
assert is_utriang([ [3,2,5],
[0,6,2],
[0,1,4] ]) == False
assert is_utriang([ [3,2,5],
[1,6,2],
[1,0,4] ]) == False
stitch_left_mod¶
This time let’s try to modify mat1
in place, by stitching mat2
to the left of mat1
.
So this time don’t put a return
instruction.
You will need to perform list insertion, which can be tricky. There are many ways to do it in Python, one could be using the weird splice assignment insertion:
mylist[0:0] = list_to_insert
see here for more info: https://stackoverflow.com/a/10623383
✪✪✪ EXERCISE: Implement stitch_left_mod
, which given the matrices mat1
and mat2
as list of lists, with mat1
of size n
x l
and mat2
of size n
x r
, MODIFIES mat1
so that it becomes of size n
x (l
+ r
), by stitching second mat2
to the left of mat1
[51]:
def stitch_left_mod(mat1,mat2):
raise Exception('TODO IMPLEMENT ME !')
m1 = [ ['a','b','c'],
['d','b','a'] ]
m2 = [ ['f','b'],
['g','h'] ]
res = [ ['f','b','a','b','c'],
['g','h','d','b','a'] ]
stitch_left_mod(m1, m2)
assert m1 == res
transpose_1¶
Let’s see how to transpose a matrix inplace. 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
funciton can also have a start index:
[52]:
list(range(3,7))
[52]:
[3, 4, 5, 6]
Also, make sure you know how to swap just two values by solving first this very simple exercise  also check the result in Python Tutor
Show solution[53]:
x = 3
y = 7
# write here code for swapping x and y (don't directly use the constants 3 and 7!)
Going back to the transpose, for now we will consider only an nxn matrix. To make sure we actually get an nxn matrix, we will validate the input as before.
IV COMMANDMENT (adapted for matrices): You shall never ever reassign function parameters
def myfun(M):
# M is a parameter, so you shall *not* do any of such evil:
M = [
[6661,6662],
[6663,6664 ]
]
# For the sole case of composite parameters like lists (or lists of lists ..)
# you can write stuff like this IF AND ONLY IF the function specification
# requires you to modify the parameter internal elements (i.e. transposing _inplace_):
M[0][1] = 6663
✪✪✪ EXERCISE If you read all the above, you can now proceed implementing the transpose_1
function, which MODIFIES the given n
xn
matrix mat
by transposing it inplace.
If the matrix is not
n
xn
, raises aValueError
[54]:
def transpose_1(mat):
raise Exception('TODO IMPLEMENT ME !')
# let's try wrong matrix dimensions:
try:
transpose_1([ [3,5] ])
raise Exception("SHOULD HAVE FAILED !")
except ValueError:
pass
m1 = [ ['a'] ]
transpose_1(m1)
assert m1 == [ ['a'] ]
m2 = [ ['a','b'],
['c','d'] ]
transpose_1(m2)
assert m2 == [ ['a','c'],
['b','d'] ]
transpose_2¶
✪✪ Now let’s try to transpose a generic nxm matrix. This time for simplicity we will return a whole new matrix.
RETURN a NEW mxn matrix which is the transpose of the given n
xm
matrix mat
as list of lists.
[55]:
def transpose_2(mat):
raise Exception('TODO IMPLEMENT ME !')
m1 = [ ['a'] ]
r1 = transpose_2(m1)
assert r1 == [ ['a'] ]
r1[0][0] = 'z'
assert m1[0][0] == 'a'
m2 = [ ['a','b','c'],
['d','e','f'] ]
assert transpose_2(m2) == [ ['a','d'],
['b','e'],
['c','f'] ]
lab¶
✪✪✪ If you’re a teacher that often see new students, you have this problem: if two students who are friends sit side by side they can start chatting way too much. To keep them quiet, you want to somehow randomize student displacement by following this algorithm:
first sort the students alphabetically
then sorted students progressively sit at the available chairs one by one, first filling the first row, then the second, till the end.
Now implement the algorithm.
INPUT:
students: a list of strings of length <= n*m
chairs: an nxm matrix as list of lists filled with None values (empty chairs)
OUTPUT: MODIFIES BOTH students and chairs inputs, without returning anything
If students are more than available chairs, raises ValueError
Example:
ss = ['b', 'd', 'e', 'g', 'c', 'a', 'h', 'f' ]
mat = [
[None, None, None],
[None, None, None],
[None, None, None],
[None, None, None]
]
lab(ss, mat)
# after execution, mat should result changed to this:
assert mat == [
['a', 'b', 'c'],
['d', 'e', 'f'],
['g', 'h', None],
[None, None, None],
]
# after execution, input ss should now be ordered:
assert ss == ['a','b','c','d','e','f','g','f']
For more examples, see tests
Show solution[56]:
def lab(students, chairs):
raise Exception('TODO IMPLEMENT ME !')
try:
lab(['a','b'], [[None]])
raise Exception("TEST FAILED: Should have failed before with a ValueError!")
except ValueError:
"Test passed"
try:
lab(['a','b','c'], [[None,None]])
raise Exception("TEST FAILED: Should have failed before with a ValueError!")
except ValueError:
"Test passed"
m0 = [ [None] ]
r0 = lab([],m0)
assert m0 == [ [None] ]
assert r0 == None # function is not meant to return anything (so returns None by default)
m1 = [ [None] ]
r1 = lab(['a'], m1)
assert m1 == [ ['a'] ]
assert r1 == None # function is not meant to return anything (so returns None by default)
m2 = [ [None, None] ]
lab(['a'], m2) # 1 student 2 chairs in one row
assert m2 == [ ['a', None] ]
m3 = [ [None],
[None] ]
lab(['a'], m3) # 1 student 2 chairs in one column
assert m3 == [ ['a'],
[None] ]
ss4 = ['b', 'a']
m4 = [ [None, None] ]
lab(ss4, m4) # 2 students 2 chairs in one row
assert m4 == [ ['a','b'] ]
assert ss4 == ['a', 'b'] # also modified input list as required by function text
m5 = [ [None, None],
[None, None] ]
lab(['b', 'c', 'a'], m5) # 3 students 2x2 chairs
assert m5 == [ ['a','b'],
['c', None] ]
m6 = [ [None, None],
[None, None] ]
lab(['b', 'd', 'c', 'a'], m6) # 4 students 2x2 chairs
assert m6 == [ ['a','b'],
['c','d'] ]
m7 = [ [None, None, None],
[None, None, None] ]
lab(['b', 'd', 'e', 'c', 'a'], m7) # 5 students 3x2 chairs
assert m7 == [ ['a','b','c'],
['d','e',None] ]
ss8 = ['b', 'd', 'e', 'g', 'c', 'a', 'h', 'f' ]
m8 = [ [None, None, None],
[None, None, None],
[None, None, None],
[None, None, None] ]
lab(ss8, m8) # 8 students 3x4 chairs
assert m8 == [ ['a', 'b', 'c'],
['d', 'e', 'f'],
['g', 'h', None],
[None, None, None] ]
assert ss8 == ['a','b','c','d','e','f','g','h']
dump¶
The multinational ToxiCorp wants to hire you for devising an automated truck driver which will deposit highly contaminated waste in the illegal dumps they own worldwide. You find it ethically questionable, but they pay well, so you accept.
A dump is modelled as a rectangular region of dimensions nrow
and ncol
, implemented as a list of lists matrix. Every cell i
, j
contains the tons of waste present, and can contain at most 7
tons of waste.
The dumpster truck will transport q
tons of waste, and try to fill the dump by depositing waste in the first row, filling each cell up to 7 tons. When the first row is filled, it will proceed to the second one from the left , then to the third one again from the left until there is no waste to dispose of.
Function dump(m, q)
takes as input the dump mat
and the number of tons q
to dispose of, and RETURN a NEW list representing a plan with the sequence of tons to dispose. If waste to dispose exceeds dump capacity, raises ValueError
.
NOTE: the function does not modify the matrix
Example:
m = [
[5,4,6],
[4,7,1],
[3,2,6],
[3,6,2],
]
dump(m, 22)
[2, 3, 1, 3, 0, 6, 4, 3]
For first row we dispose of 2,3,1 tons in three cells, for second row we dispose of 3,0,6 tons in three cells, for third row we only dispose 4, 3 tons in two cells as limit q=22 is reached.
Show solution[57]:
def dump(mat, q):
raise Exception('TODO IMPLEMENT ME !')
m1 = [ [5] ]
assert dump(m1,0) == [] # nothing to dump
m2 = [ [4] ]
assert dump(m2,2) == [2]
m3 = [ [5,4] ]
assert dump(m3,3) == [2, 1]
m3 = [ [5,7,3] ]
assert dump(m3,3) == [2, 0, 1]
m5 = [ [2,5], # 5 2
[4,3] ] # 3 1
assert dump(m5,11) == [5,2,3,1]
# tons to dump in each cell
m6 = [ [5,4,6], # 2 3 1
[4,7,1], # 3 0 6
[3,2,6], # 4 3 0
[3,6,2] ] # 0 0 0
assert dump(m6, 22) == [2,3,1,3,0,6,4,3]
try:
dump ([[5]], 10)
raise Exception("Should have failed !")
except ValueError:
pass
matrix multiplication¶
Have a look at matrix multiplication definition on Wikipedia and try to implement it in the following function.
Basically, given nxm matrix A and mxp matrix B you need to output an nxp matrix C calculating the entries \(c_{ij}\) with the formula
\(c_{ij} = a_{i1}b_{1j} +\cdots + a_{im}b_{mj}= \sum_{k=1}^m a_{ik}b_{kj}\)
You need to fill all the nxp cells of C, so sure enough to fill a rectangle you need two for
s. Do you also need another for
? Help yourself with the following visualization.
✪✪✪ EXERCISE: Given matrices n
x m
mata
and m
x p
matb
, RETURN a NEW n
x p
matrix which is the result of the multiplication of mata
by matb
.
If
mata
has column number different frommatb
row number, raises aValueError
.
[58]:
def mul(mata, matb):
raise Exception('TODO IMPLEMENT ME !')
# TEST START  DO NOT TOUCH!
# if you wrote the whole code correct, and execute the cell, Python shouldn't raise `AssertionError`
# let's try wrong matrix dimensions:
try:
mul([[3,5]], [[7]])
raise Exception("SHOULD HAVE FAILED!")
except ValueError:
"passed test"
ma1 = [ [3] ]
mb1 = [ [5] ]
r1 = mul(ma1,mb1)
assert r1 == [ [15] ]
ma2 = [ [3],
[5] ]
mb2 = [ [2,6] ]
r2 = mul(ma2,mb2)
assert r2 == [ [3*2, 3*6],
[5*2, 5*6] ]
ma3 = [ [3,5] ]
mb3 = [ [2],
[6] ]
r3 = mul(ma3,mb3)
assert r3 == [ [3*2 + 5*6] ]
ma4 = [ [3,5],
[7,1],
[9,4] ]
mb4 = [ [4,1,5,7],
[8,5,2,7] ]
r4 = mul(ma4,mb4)
assert r4 == [ [52, 28, 25, 56],
[36, 12, 37, 56],
[68, 29, 53, 91] ]
check_nqueen¶
✪✪✪✪ This is a hard problem but don’t worry, exam exercises will be simpler!
You have an nxn matrix of booleans representing a chessboard where True means there is a queen in a cell,and False there is nothing.
For the sake of visualization, we can represent a configurations using o
to mean False
and letters like ‘A’ and ‘B’ are queens. Contrary to what we’ve done so far, for later convenience we show the matrix with the j
going from bottom to top.
Let’s see an example. In this case A and B can not attack each other, so the algorithm would return True
:
7 ......B.
6 ........
5 ........
4 ........
3 ....A...
2 ........
1 ........
0 ........
i
j 01234567
Let's see why by evidencing A attack lines ..
7 \....B.
6 .\..../
5 ..\../.
4 ...\/..
3 A
2 .../\..
1 ../..\.
0 ./....\
i
j 01234567
... and B attack lines:
7 B
6 ...../\
5 ..../..
4 .../...
3 ../.A..
2 ./.....
1 /......
0 .......
i
j 01234567
In this other case the algorithm would return False as A
and B
can attack each other:
7 \./....
6 B/
5 /\../.
4 ..\/..
3 A
2 ../\..
1 ./..\.
0 ./....\
i
j 01234567
In your algorithm, first you need to scan for queens. When you find one (and for each one of them !), you need to check if it can hit some other queen. Let’s see how:
In this 7x7 table we have only one queen A, with at position i=1
and j=4
6 ......
5 \.....
4 .\....
3 ..\../
2 ...\/.
1 A
0 .../\.
i
j 0123456
To completely understand the range of the queen and how to calculate the diagonals, it is convenient to visually extend the table like so to have the diagonals hit the vertical axis. Notice we also added letters y
and x
NOTE: in the algorithm you do not need to extend the matrix !
y
6 ........
5 \....../
4 .\..../.
3 ..\../..
2 ...\/...
1 A
0 .../\...
1 ../..\..
2 ./....\.
3 /......\
i
j 01234567 x
We see that the topleft to bottomright diagonal hits the vertical axis at y = 5
and the bottomleft to topright diagonal hits the axis at y = 3
. You should use this info to calculate the line equations.
Now you should have all the necessary hints to proceed with the implementation.
Show solution[59]:
def check_nqueen(mat):
""" Takes an nxn matrix of booleans representing a chessboard where True means there is a queen in a cell,
and False there is nothing. RETURN True if no queen can attack any other one, False otherwise
"""
raise Exception('TODO IMPLEMENT ME !')
assert check_nqueen([ [True] ])
assert check_nqueen([ [True, True],
[False, False] ]) == False
assert check_nqueen([ [True, False],
[False, True] ]) == False
assert check_nqueen([ [True, False],
[True, False] ]) == False
assert check_nqueen([ [True, False, False],
[False, False, True],
[False, False, False] ]) == True
assert check_nqueen([ [True, False, False],
[False, False, False],
[False, False, True] ]) == False
assert check_nqueen([ [False, True, False],
[False, False, False],
[False, False, True] ]) == True
assert check_nqueen([ [False, True, False],
[False, True, False],
[False, False, True] ]) == False
[ ]: