2-Dimensional Lists

Tasks

1. Complete reading this lesson, which involves the following:
   1. Basics of Two Dimensional Lists
   2. Manipulating Two Dimensional Lists
   3. Problem Solving Using Two Dimensional Lists
2. Complete quiz 10 to verify your reading and understanding.
3. Read and complete the activities at Zybook, Z11: Two Dimensional Lists.

Learning Outcomes

By the end of this lesson, you should be able to:

1. Construct and initialize two dimensional lists.
2. Access and update elements in two dimensional lists.
3. Use nested loops to manipulated two dimensional lists.
4. Use two dimensional lists in problem solving.

Key Terms/Concepts

• 2D List, matrix, array, row, columns, inner and outer lists.

Introduction

The concept of two dimensional lists is an essential programming technique that relates to the concept of matrices in mathematics. It is a relatively advanced concept because it combines the concept of lists with the concept of nested loops. But if you understand these two concepts, you will find studying two dimensional lists an entertaining experience.

Matrices are composed of rows and columns. That is exactly what should come to your mind when you think of two dimensional lists: a group of rows and group of columns. If you picture these rows and columns, then you can project 2D lists into many applications beyond matrices (This should be motivational to you if you did not like that topic of matrices in mathematics).

For example, tables are structured using 2D lists. Also, many storage cabinets are structured in rows and columns which we can capture in 2D lists. An instructor trying to divide the class into groups each with 5 students should be able to achieve that using 2D lists. A photo of a rectangular parking lot can be analyzed in 2D lists. The list goes on. 

If you are learning this topic for the first time, I have two recommendations for you. Firstly, whenever you get lost in tracing your 2D list, take a paper and pencil and do it by hand. Do not leave it all in your head. It is an echo of a similar advice given when studying loops. Second, follow the standard systematic approach to manipulating lists: two nested for loops, the outer for loop is for accessing rows using variable i and the inner loop is for accessing columns using variable j. This is not the only method to manipulate 2D lists, but it is simple enough and has been used across most programming manuals. When you become handy with 2D lists, you can divert from this standard form to using while loops, using different loop variables and more refined controls of the nested loop.

This lesson has a simple structure. In the following section the basics of creating and accessing elements in 2D lists will be presented. Section 11.3 will focus on using nested loops to manipulate 2D lists. Finally, Section 11.4 will present some problems where 2D lists provide a nice and effective solution.

Let us start.

2D List Basics

11.2.1 Understanding 2D Lists in Python

When you learned about lists in Lesson 8, you found that Python does not put restrictions on the type of elements enclosed in a list. A list can contain numbers, strings or a mix of both. This interesting flexibility allows a list to also contain other lists. This is where the discussion on 2D lists start.

In a 2D list, all elements in the list are also lists. For instance, all of the following are 2D lists:

[ [1,2], [3,5] ]
[ [‘a’,’b’,’c’] , [‘d’,’e’,’f’] ]
[ [10] , [20] , [30] , [40] , [50] ]
[ [] , [] ]

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

We will call the parent list which encompasses the other lists as the outer list, and the enclosed lists as inner lists. Each inner list is an element in the outer list.

Python is one of the most liberal languages when it comes to defining lists. As highlighted in the above technical note, there is no restriction that all inner lists should either be lists or non-lists. Also, there is no restriction on the length of inner lists. The inner lists can share the same length or have different lengths.

For example, the following are valid Python lists:

[ [1], [2,3], [4,5,6] ]
[ [‘a’,’b’,’c’] , [] , [‘d’,e’,f’] ]

Even more, lists can have mixed types, like:

[ [1], [‘str1’,’str2’], [4.0,5.0,6.0] ]
[ [‘a’,’b’,’c’] , [] , [1,2,3] ]

If you are wondering if we can get even more flexible than this, check the following technical note.

[ [ [1,2],[3,4] ], [ [5,6],[7,8] ] ]

In many programming languages, it is common to refer to lists that has homogenous data type as an array. Also, a two dimensional list in which all inner lists share the same length (and are mainly composed of numbers) are called matrices. In Python, all of these are referred to as lists.

In this lesson, we are specifically interested in two dimensional lists in which all inner lists share the same length. In these lists we say it has a size of r x c, where r represents the number of rows and c represents the number of columns.  

11.2.2 Constructing 2D Lists

A two dimensional list can be directly assigned to a variable, just like assigning any other value. For instance, we can assign a 2x3 matrix containing all zeros to the variable x using the following command:

x = [ [0,0,0] , [0,0,0] ]

That is straight-forward and simple!

However, how would you create a 100x50 matrix containing all zeros? The above direct method would not be practical anymore.

There is a simple line of code which we can use to create such lists, which is:

x = [ [0]*50 ] * 100

The expression [0] * 50 generates a one dimensional list containing 50 elements, each equal to zero. This is similar to creating one row containing 50 columns. When this is multiplied by a 100, it creates 100 rows, each containing 50 zeros.

Using the same logic, we can generalize:

x = [ [0]*c ] * r

where r is the number of rows and c is the number of columns.

Using a similar syntax, try generating a 50 x 3 list where each row contains [1,2,3].

The above methods are good when all elements are the same, or when all rows are small and have similar content. If elements of the 2D lists are arbitrary, the above method does not work. Also, the above method creates a 2D list using copy by reference, which is problematic if you attempt to modify the contents. Therefore, we will resort to using nested loops (see section 11.3). Using nested loops would require more work but is proved to work for various applications and avoids the copy by reference issue.

Before introducing the nested loops, we will demonstrate how to perform basic access operations on 2D lists.

11.2.3 Accessing Elements

If you have a 2D list, and would like to access a specific element, then the following syntax can be used:

<list name>[i][j]

where i represent the row number and j represent the column number. 

For example, if you would like to print element 50 in the following 2D list:

x = [[10,20],[30,40],[50,60]]

Then you can use the following command:

print(x[2][0])

Since element 50 is located at the 2^nd row and 0^th column, then it can be accessed by x[2][0]. Remember, we number elements in lists starting from index 0 not 1.

The above access method leads us to another observation. What happens if we execute the following command?

print(x[2])

The above command prints the 2^nd element in the list x. But what is that element? If you think carefully, you will find that it refers to the 2^nd inner list. Therefore, the output will be:

[50,60]

This can be generalized by interpreting the following syntax:

<list  name>[i]

as accessing the i^th row in the list.  

Up to this point, you saw how to access elements and rows in a list. What remains is how to access columns. Unlike elements and rows, there is no simple command to access columns. We will need to use loops for that purpose.

To print the j^th column in a 2D list, we can use the following command:

for i in range(r): 
    print(<list name>[i][j])

In the above command: the variable j, which represents the column number, is fixed while i, which represents the row number, is changing with every iteration, starting from 0 up to the number of rows. The variable r represents the number of rows.

We will conclude this section by showing an example of how to access a 2D list, this time changing the element values instead of printing.

Example 11.2:

Implement the function increment(num_list,type,n).

The function receives a 2D list containing numbers. Assume that the 2D list is a non-empty matrix. If the value of t (short name for type) is 'r', then the function increments all values in the n^th row. If the value of t is 'c', then the function increments all values in the n^th column. If the user provides an invalid type, the function prints an error message and returns.

The solution to the above function is as follows:

# Program Name: Prog 11-01
# Solution to Example 11.2
 
def increment(num_list, t, n):
    r = len(num_list)
    c = len(num_list[0])
    if t == 'r':
        for j in range(c):
            num_list[n][j] += 1
    elif t == 'c':
        for i in range(r):
            num_list[i][n] += 1
    else:
        print('Error: Invalid type')
    return

In the first two commands in the function, we find the number of rows and number of columns. The number of rows is similar to the number of inner lists, which can be found using len(num_list). Since the input is assumed to be a matrix, then all inner lists have the same length. Therefore, we can find the number of columns by taking the length of any inner list. The above solution uses: len(num_list[0]). We can safely use the first row because we are assuming that the input is always non-empty. This is not the case for the other rows, which may or may not exist.

If the user chooses to increment a row, i.e t = 'r', then we need a loop to iterate through all columns for the specified row. Here the row is fixed (n), while the column number (j) iterates from 0 up to column length.

If the user chooses to increment a column, i.e. t = 'c', then we need a loop to iterate through all rows and access the specified column. Here the column is fixed (n), while the row number (i) iterates from 0 up to row length.

Finally, if the user provides any other value for t, then an error message is printed.

Note that the function does not return anything, because the list is passed by reference. This concept was discussed in Lesson 8.

To test the above program, we can use a code similar to the following:

num_list = [[1,2],[3,5],[6,7],[8,9]]
print('list before increment:')
print(num_list)

increment(num_list,'r',0)
print('list after increment(num_list,"r",0):')
print(num_list)

increment(num_list,'c',1)
print('list after increment(num_list,"c",1):')
print(num_list)

print('list after increment(num_list,"d",1):')
increment(num_list,'d',1)
print(num_list)

Running the above testing code produces the following output:

list before increment:
[[1, 2], [3, 5], [6, 7], [8, 9]]
list after increment(num_list,"r",0):
[[2, 3], [3, 5], [6, 7], [8, 9]]
list after increment(num_list,"c",1):
[[2, 4], [3, 6], [6, 8], [8, 10]]
list after increment(num_list,"d",1):
Error: Invalid type
[[2, 4], [3, 6], [6, 8], [8, 10]]

Manipulating 2D Lists

In this section, we will build on the concepts presented in the previous section, but in more depth. We will be using nested loops to manipulate 2D lists. The generic form is presented first, followed by three examples. The term manipulate is used loosely to include any access or change operation.

11.3.1 General Form

The general form to manipulate 2D lists is the following:

for i in range(r):
    for j in range(c):
        <list name>[i][j] = ?

The outer loop runs through all rows in the list, while the inner loop runs through all columns within that row. The variables r and c represent the number of rows and columns as mentioned earlier. The variables i and j are used to iterate through rows and columns, respectively.

The above form is the most important concept in this lesson. If you understand it, then you understand 2D lists, and the reverse is also true. Therefore, we will give three examples that directly use the generic form.

11.3.2 Printing a 2D List

Example 11.3.A:

Implement the function print_2D(input_list).

The function receives an arbitrary 2D list. The function prints the 2D list, such that each row appears on a separate line, and row elements are separated by a tab.

The solution to the above example is as follows:

# Program Name: Prog 11-02
# Solution to Example 11.3.A
 
def print_2D(my_list):
    for i in range(len(my_list)):
        for j in range(len(my_list[0])):
            print(f'{my_list[i][j]}',end='\t')
        print()
    return

num_list = [[1,2],[3,5],[6,7],[8,9]]
print('list1 =')
print_2D(num_list)
print()

num_list = [[10,20,30,40],[50,60,70,80]]
print('list2 =')
print_2D(num_list)

The above code is a direct application of the generic form. Instead of using two separate commands to find the number of rows (r) and number of columns (c), we plugged in the lengths directly in the loops. Also, an additional line was added after the second loop to print an empty line. This command is enclosed within the outer loop. Therefore, it is executed once for each row.

Running the above code would produce the following output:

list1 =
1   2   
3   5   
6   7   
8   9   

list2 =
10  20  30  40  
50  60  70  80  

11.3.3 Searching a 2D List

Example 11.3.B:

Implement the function search_2D(input_list, item).

The function receives an arbitrary 2D list and an item to search. The function inspects all items in the list. If the item is found, it returns True and returns False otherwise.

The solution to the above example is as follows:

# Program Name: Prog 11-03
# Solution to Example 11.3.B
 def search_2D(input_list, item):
    result = False
    for i in range(len(input_list)):
        for j in range(len(input_list[i])):
            if input_list[i][j] == item:
                result = True
                break
    return result

input_list = [[77,51],[60,37,41],[92,67],[5],[88,9,11,74,68]]
print('input_list =')
print(input_list)
print()

print(f'search_2D(input_list,41) = {search_2D(input_list,41)}')
print(f'search_2D(input_list,5) = {search_2D(input_list,5)}')
print(f'search_2D(input_list,68) = {search_2D(input_list,68)}')
print(f'search_2D(input_list,55) = {search_2D(input_list,55)}')
print(f'search_2D(input_list,1) = {search_2D(input_list,1)}')

The above solution is another application of the generic form. However, we would like to highlight one minor difference.

In this problem, we need to consider a 2D list with variable lengths of the inner list, because it is not stated in the question that it is a matrix. The expression len(input_list[i]) in the second loop handles this. At every iteration of the outer loop, the i^th row is picked. The second loop specifies the number of iterations based on the length of that row. 

The output of running the above code is:

input_list =
[[77, 51], [60, 37, 41], [92, 67], [5], [88, 9, 11, 74, 68]]

search_2D(input_list,41) = True
search_2D(input_list,5) = True
search_2D(input_list,68) = True
search_2D(input_list,55) = False
search_2D(input_list,1) = False

11.3.4 Find-Replace in a 2D List

In the previous two examples, we accessed the 2D list, but without changing its contents. In this example, we will search the 2D list along with modifying its contents.

Example 11.3.C:

Implement the function replace_2D(input_list, old_value, new_value).

The function receives an arbitrary 2D list and two data items. The function inspects all items in the list, and replaces every instance of old_value with new_value. The function returns number of replacements made.

Ungraded Self-Assessment Question

This time try to write the code yourself before checking the solution. Use the following code to test your solution, and then click on the Answer button below to check. This activity is not graded, but it is essential for your self-assessment, and it will help you prepare for upcoming quizzes and assignments.

input_list = [[1,2],[3,4,5],[3,4],[5],[1,2,3,4,5]]
print('input_list =')
print(input_list)
print()

print('replace_2D(input_list,1,10) = ')
count = replace_2D(input_list,1,10)
print(input_list)
print(f'#replacements = {count}')
print()

print('replace_2D(input_list,5,50) = ')
count = replace_2D(input_list,5,50)
print(input_list)
print(f'#replacements = {count}')
print()

print('replace_2D(input_list,9,90) = ')
count = replace_2D(input_list,9,90)
print(input_list)
print(f'#replacements = {count}')

# Program Name: Prog 11-04
# Solution to Example 11.3.C
 
def replace_2D(input_list, old_value, new_value):
    counter = 0
    for i in range(len(input_list)):
        for j in range(len(input_list[i])):
            if input_list[i][j] == old_value:
                input_list[i][j] = new_value
                counter += 1
    return counter

input_list =
[[1, 2], [3, 4, 5], [3, 4], [5], [1, 2, 3, 4, 5]]

replace_2D(input_list,1,10) = 
[[10, 2], [3, 4, 5], [3, 4], [5], [10, 2, 3, 4, 5]]
#replacements = 2

replace_2D(input_list,5,50) = 
[[10, 2], [3, 4, 50], [3, 4], [50], [10, 2, 3, 4, 50]]
#replacements = 3

replace_2D(input_list,9,90) = 
[[10, 2], [3, 4, 50], [3, 4], [50], [10, 2, 3, 4, 50]]
#replacements = 0

Problem Solving

In this section, we will present four problems that require using 2D lists. The first two problems handle creating a phonebook and then doing some queries. The second two problems are applications on mathematical matrices. By going through these problems, along the ones presented in the previous section, we are hoping that your understanding of the topic is solidified. You can imitate the approaches used here in other problems that you may encounter in the future.

11.4.1 Create a Phone Book

Example 11.4.A:

Implement the function create_phonebook(). The function contains a loop that keeps asking the user for a name and phone number and stops when the user enters 'stop'. The names and phones are stored in a 2D list (phonebook), which contains the name-list as the first element and phone-list as the second element. The function returns the created phonebook.

Also implement the function print_phonebook(phonebook), which prints the contents of a phonebook, such every record (name: phone) appear on a separate line.

We will start by implementing the create_phonebook function. Below is one way to code it:

def create_phonebook():
    names = []
    phones = []
    
    name = input('Enter name: ')
    while name != 'stop':
        names.append(name)
        phone = input('Enter phone: ')
        phones.append(phone)
        print()
        name = input('Enter name: ')
    phonebook = [names,phones]    
    return phonebook

Because a phonebook is to be constructed, as per the instructions, such that all names appear in one list and all phone numbers appear on the second, we decided to create two separate lists and then join them in one 2D list.

If the question asked to format the phonebook such that the 2D list contains each record [name, phone] separately, then the solution would be like the following:

def create_phonebook2():
    phonebook = [] 
    name = input('Enter name: ')
    while name != 'stop':
        record = []
        record.append(name)
        phone = input('Enter phone: ')
        record.append(phone)
        phonebook.append(record)
        print()
        name = input('Enter name: ')  
    return phonebook

Next, we implement the printing function. Other than the requirement to have every entry on a separate line, we have flexibility on how to print the records. The following code prints the phonebook in a good formatting:

def print_phonebook(phonebook):
    print(f"{'Name':^13s}\t{'Phone':^13s}")
    print(f"{'-'*13}\t{'-'*13}")
    count = len(phonebook[0])
    for i in range(count):
        name = phonebook[0][i]
        phone = phonebook[1][i]
        print(f'{name:13s}\t{phone:13s}')
    return

Note how in the above printing function, at each iteration, we are accessing a name and a phone number from the two inner lists. At the i^th iteration, we are picking the i^th entry in the first inner list which denotes a name, and the i^th entry in the second inner list, which denotes a phone number. The combination of name-number is printed, then the loop moves to the next entry.

Running both functions will yield an output similar to the following:

Enter name: David Smith
Enter phone: 939-111-0000

Enter name: Lucy Ryan
Enter phone: 783-222-1111

Enter name: Ruby Fann
Enter phone: 621-333-4444

Enter name: stop
    Name            Phone    
-------------   -------------
David Smith     939-111-0000 
Lucy Ryan       783-222-1111 
Ruby Fann       621-333-4444 

11.4.2 Query a Phone Book

Example 11.4.B:

Implement the function query_phonebook(phonebook, character). The function receives a phonebook and a character. The function searches the phonebook for all entries that start with the given character. A 2D list is created and returned containing all entries that start with the given character.

In this problem we need to access the phonebook 2D list and also create a new 2D list. We saw how to create a phonebook (Example 11.4.A) and also how to access a 2D list (Example 11.3.B). We need to combine both techniques to solve this problem.

Below is the solution:

# Program Name: Prog 11-05
# Solution to Example 11.4.B

def query_phonebook(phonebook, character):
    output_phonebook = [[],[]]
    for i in range(len(phonebook[0])):
        name = phonebook[0][i]
        if name[0] == character:
            output_phonebook[0].append(phonebook[0][i])
            output_phonebook[1].append(phonebook[1][i])
    return output_phonebook

The first line in the function creates an empty phonebook with two empty inner lists. The first one will be used to store names and the second to store phone numbers.

To find out the number of records in the input phonebook, we can use len(phonebook[0]) or len(phonebook[1]). We plugged in this value directly to the loop, unlike the previous example where we used the variable count.

To check the first character of the name, we first retrieved the name from the phonebook then accessed the first character in the if statement. We could have used a command like the following:

if phonebook[0][i][0] == character:

But that would have provided poor readability.

Once a matching record was found, the output phonebook two inner lists are appended with the current name and phone number.

To test the above function, we will use a manually created phonebook along with the print_phonebook function that was created in Section 11.4.1. The testing code is as follows:

phonebook = [['David Smith', 'Ruby Fann', 'Sally Phu', 'Rania Kin', 'Daniel Peter', 'Hei Ng', 'Robel James', 'Sean Wall'],          ['11111111','22222222','33333333','44444444','55555555','66666666','77777777','88888888']]
print_phonebook(phonebook)
print()

print('Query "D":')
phonebook1 = query_phonebook(phonebook,'D')
print_phonebook(phonebook1)
print()

print('Query "R":')
phonebook1 = query_phonebook(phonebook,'R')
print_phonebook(phonebook1)
print()

print('Query "P":')
phonebook1 = query_phonebook(phonebook,'P')
print_phonebook(phonebook1)
print()

The output of running the above code is as follows:

    Name            Phone    
-------------   -------------
David Smith     1111111   
Ruby Fann       2222222   
Sally Phu       33333333     
Rania Kin       44444444     
Daniel Peter    55555555     
Hei Ng          66666666     
Robel James     77777777     
Sean Wall       88888888     

Query "D":
    Name            Phone    
-------------   -------------
David Smith     1111111   
Daniel Peter    55555555     

Query "R":
    Name            Phone    
-------------   -------------
Ruby Fann       2222222   
Rania Kin       44444444     
Robel James     77777777     

Query "P":
    Name            Phone    
-------------   -------------

11.4.3 Identity Matrix

Example 11.4.C:

Implement the function identity(size). The function creates an identity matrix with the given size. An identity matrix is a matrix in which all elements are zero except the diagonal line (from top left to bottom right) which contains 1's. The following are examples of identity matrices with various sizes:

identity(0) -> ‘Error’
Identity(1) -> [1]
identity(2) -> [ [1,0], [0,1] ]
identity(3) -> [ [1,0,0], [0,1,0], [0,0,1] ] 

The function returns the created identity matrix. If there is an error, the function returns an empty matrix.

One simple approach to solve the above problem is to create a zero matrix, then set the diagonal elements to 1. Study the following code:

def identity(size):
matrix = []
if size <= 0:
print('Error: invalid size')
elif size == 1:
matrix = [1]
else:
for i in range(size):
matrix.append([])
matrix[i] = [0] * size
for i in range(size):
matrix[i][i] = 1
return matrix

The first if statement handles the scenario when the size is invalid, i.e. smaller than zero. The function prints an error message and returns an empty list.

The elif statement handles the special scenario when size is 1. This is the only case when the function returns a one dimensional list instead of a 2D list.

The else statement starts by creating a square matrix with the given size and initializes all elements to 0. To achieve that, an empty inner list is appended to the outer list, then it is filled with zero elements. The second loop accesses the diagonal elements and set it to 1.

To test the function, we can use a simple loop like the following:

for i in range(5):
print(f'identity({i}) = {identity(i)}')

The above loop produces identity matrices starting from size 0 to size 4. Below is the output:

Error: invalid size
identity(0) = []
identity(1) = [1]
identity(2) = [[1, 0], [0, 1]]
identity(3) = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
identity(4) = [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]

11.4.4 Uniform Matrix

Example 11.4.D:

Implement the function is_uniform(matrix). The function receives a non-empty matrix and inspects its element to check if it is uniform. A uniform matrix is a matrix in which all its elements share the same value. By default, a matrix of size 1x1 is a uniform matrix. The function returns True or False.

The above problem can be solved using the generic form. Excluding the special case when the matrix is of size 1x1, we can loop through all elements in the list and compare them to the first element. At any instance, if the function detects non-equality the function stops and returns False. If the loop finishes without interruption, then this indicates that all elements are equal.

Below is one way to code the above strategy:

def is_uniform(matrix):
result = True
if len(matrix) >= 2:
for i in range(len(matrix)):
for j in range(len(matrix[0])):
    if matrix[i][j] != matrix[0][0]:
        result = False
        break
return result

If the input is a matrix of size 1x1, result is initialized to True. The conditional if statement will return False and will be skipped. The function returns True.

If the input is a matrix of larger size, result is initialized to True and the function executes the if statement. The nested loops traverse through all elements in the matrix, at each iteration comparing the current element to the first element in the matrix. If non-equality is detected, result is set to False and the loop breaks. The function returns False.

If all elements are equal, the nested loop will complete without setting result to False. Therefore, the function returns the default value of result which is True. 

Testing the above solution will yield the following output:

is_uniform([9])? = True
is_uniform([[2,2],[2,2]])? = True
is_uniform([[4,3],[4,4]])? = False
is_uniform([[1,1,1],[1,1,1],[1,1,1]])? = True
is_uniform([[1,1,1],[1,1,6],[1,1,1]])? = False

Conclusion

In Lesson 11, you learned about Python two dimensional lists. You could now create 2D lists using the direct method or using nested loops. You can now access rows, columns and elements in a 2D list. You are familiar with the generic form that uses two nested for loops to iterate through all items in a 2D list. You can use this generic form to develop various solutions to manipulate lists. You encountered problems that require inspecting 2D list elements, searching a 2D list and updating the contents of 2D list. These solutions can be used as a platform to develop similar solutions to future problems that you may encounter which require using 2D lists.

Check Weekly Schedule for Assessments