Homework for Week 11
Nested lists and nested loops
So far we have studied single (non-nested) lists and loops. But in fact, lists can be used inside lists (list elements are other lists) and loops can be written inside loops.
Please read this material before the session. While reading, study the code, run it, change it and rerun it!
Nested lists
A nested list is a list which is inside of another list. In the following example, the element at index 3 is a nested list:
nested = ["hello", 2.0, 5, [10, 20]]
If we output the element at index 3
nested = ["hello", 2.0, 5, [10, 20]] print(nested[3])
we get [10, 20].
To extract an element from the nested list, we have to perform two steps:
elem = nested[3] # the result is [10, 20] print(elem[0]) # the result is 10
Or merge these steps as:
print(nested[3][0])
Bracket operators evaluate from left to right. In the example above, Python takes the fourth element (with index 3) of list and then extracts the first element (with index 0) of it.
Matrices
Nested lists are often used to represent matrices. For example, the matrix:
{$$\pmatrix{1&2&3\\4&5&6\\7&8&9}$$}
might be represented as:
mx = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Here, mx is a list with three elements, each element is a row of the matrix. We can select an entire row from the matrix:
print(mx[1]) # the result is [4, 5, 6]
Or we can extract a single element from the matrix using the double-index notation:
print(mx[1][2]) # the result is 6
The first index points to the row, and the second index points to the column.
Although this way of representing matrices is common, it is not the only one. Later we will learn about dictionaries.
Next questions are meant for self-assessment. Try to figure out the correct answer. Also, it is useful to look at the explanations for wrong answers as well.
Nested loops
Python also allows to use a loop inside another loop. A nested loop is a loop that is placed inside the body of another loop. The following lines summarise main concepts of inner and outer loops:
for [first_iterating_variable] in [outer_loop]: # Outer loop
[do something] # Optional
for [second_iterating_variable] in [inner_loop]: # Inner loop
[do something]
[do something] # Optional
First, the program executes the first iteration of the outer loop. The first iteration triggers the inner, nested loop. The inner loop runs through all its iterations until the end. Then the program returns back to the outer loop. The second pass of the outer loop triggers the inner loop again. This repeats until the outer loop finishes or a break or other statement disrupts the process.
The next example gives a closer look at nested for loop. Here, the outer loop iterates through a list of integers called num_list, the inner loop iterates through a list of strings called alpha_list.
num_list = [1, 2, 3]
alpha_list = ['a', 'b', 'c']
for number in num_list:
print(number, end=" ")
for letter in alpha_list:
print(letter, end=" ")
The output of this program is:
1 a b c 2 a b c 3 a b c
The output illustrates that the program completes the first iteration of the outer loop by printing 1, which then triggers the inner loop, printing a, b, c, consecutively. Once the inner loop is completed, the program returns to the outer loop, prints 2, then again executes the inner loop in its entirety (a, b, c), etc.
Nested for loops can be used to iterate through the items within lists composed of lists (matrices). In other words, if we employ just one for loop in a matrix, the program will output each internal list as one element:
mx = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
for li in mx:
print(li)
Output:
[1, 2, 3] [4, 5, 6] [7, 8, 9]
In order to access each element of the internal lists, a nested for loop is used:
mx = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
for li in mx:
for item in li:
print(item, end=" ")
Output:
1 2 3 4 5 6 7 8 9
Moreover, nested loops are often used to loop over nested lists. It is an old tradition to use i as an iteration variable of the outer loop and j as an iteration variable of the inner loop. Consider the following example:
mx = [[1, 2, 3, 4], [5, 6], [7, 8, 9]]
for i in range(len(mx)):
for j in range(len(mx[i])):
print(mx[i][j], end=" ")
print()
In the outer loop, i takes the values in the range between 0 and len(mx) - 1. For each value of i, the inner loop runs through all indices of i'th row, from 0 to len(mx[i]) - 1. The elements mx[i][j] depend on the value of j. Importantly, the program works irrespectively of row size – iteration variable j takes the values depending on the length of the current row.
One more example of nested for loop (try it):
for x in range(1, 11):
for y in range(1, 11):
print(x*y,"\t", end=" ")
print()
Analogously, programs can use nested while loops with similar syntax:
while [expression_of_outer_loop]: # Outer loop
[do something] # Optional
while [expression_of_inner_loop]: # Inner loop
[do something]
[do something] # Optional
You can put any type of loop inside of any other type of loop. For example a for loop can be inside a while loop or vice versa.
Quiz
Go to Moodle and solve the quiz on nested loops.
Exercises
1. Table
Write a function print_table() which takes two lists of one-symbol strings as arguments and prints a table of all pairs that can be formed by "pairing" the elements of these lists:
>>> print_table(['1', '2', '3'], ['a', 'b', 'c']) 1a 1b 1c 2a 2b 2c 3a 3b 3c
There should be one space between each two adjacent pairs in a row and no space between the elements inside pairs.
2. Queue in a food store
A number of people stand in a food store queue. A list contains the numbers of products in their baskets. Write a function more_than_three() that for each person in the queue finds the number of people in front of him/her that have more than three products in their baskets.
The function should have one parameter – a list of positive integers. It should return a list of the same length, where each element is the number of people who stand in the queue before that person and have more that three products in their baskets.
>>> more_than_three([5, 2, 1, 8, 21, 7, 3, 4]) [0, 1, 1, 1, 2, 3, 4, 4] >>> more_than_three([4, 4, 4, 4, 4]) [0, 1, 2, 3, 4]
3. Number of wins
Write a function number_of_wins() that takes a 4×4 matrix of symbols X and O as its argument; the matrix descibes a position in a 4×4 tic-tac-toe game. The function returns a list of two integers, where the first integer shows how many possibilities are there to find a row of 3 consecutive symbols X either horizontally, vertically or diagonally, and the second integer shows the same for the symbol O.
Example 1
>>> number_of_wins([['X','X','X',' '],
[' ','O',' ',' '],
[' ',' ','O',' '],
[' ',' ',' ','O']])
[1, 1]
Example 2
>>> number_of_wins([['O',' ',' ','X'],
[' ','O','X',' '],
[' ','X','O',' '],
['X',' ',' ','O']])
[2, 2]
(There are two sets of three consecutive X's on the diagonal: first three elements and last three elements, and the same with O's.)
Example 3
>>> number_of_wins([[' ',' ',' ',' '],
[' ',' ',' ',' '],
[' ',' ',' ',' '],
[' ',' ',' ',' ']])
[0, 0]
Example 4
>>> number_of_wins([['O',' ','O','X'],
['O','O','X','X'],
['O','X','O',' '],
['X','X','X','O']])
[3, 4]
The position may not represent an actual position in the game: the numbers of X's and O's may differ by more than one.
Hint: there is no need to write extensive if-statements.
Submit your solutions
Go to Moodle and submit your solutions of exercises as under Homework of week 11.