6.5 Nested iterations

Nested iterations in Python refer to having one loop inside another loop. This technique is commonly used when you need to perform repeated actions on a multi-dimensional structure, such as a list of lists (2D lists) or when you need to compare all elements of one sequence with all elements of another sequence.

6.5a Why Do We Need Nested Iterations?

• Handling Multi-dimensional Data Structures - Nested loops are essential for iterating through multi-dimensional data structures like matrices or grids. For example, if you have a 2D list (a list of lists), you use nested loops to access each element.

• Complex Algorithms - Some algorithms inherently require nested loops. Examples include sorting algorithms like bubble sort, insertion sort, or selection sort, which involve comparing each element with others.

• Cross-Product Operations - When you need to compute the Cartesian product of two sets or lists, nested loops allow you to generate all possible pairs of elements.

• Combinations and Permutations - Generating combinations or permutations of a set of elements typically involves nested loops.

Example 6.5.1 - Iterating through a 2D list

Here's a simple example of nested iterations to print each element of a 2D list.

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

for row in matrix:
    for element in row:
        print(element, end=' ')
    print()  # Print a new line after each row

Example 6.5.1 - Output

1 2 3 
4 5 6 
7 8 9

Example 6.5.2 - Generating Cartesian Product

Here's an example of generating all pairs from two lists using nested loops.

list1 = [1, 2, 3]
list2 = ['a', 'b', 'c']

for item1 in list1:
    for item2 in list2:
        print(f"({item1}, {item2})")

Example 6.5.2 - Output

(1, a)
(1, b)
(1, c)
(2, a)
(2, b)
(2, c)
(3, a)
(3, b)
(3, c)

Example 6.5.3 - Creating a Multiplication Table Here's another example to generate a multiplication table using nested loops.

for i in range(1, 6):
    for j in range(1, 6):
        print(f"{i * j:2}", end=' ')
    print()  # Print a new line after each row

Example 6.5.3 - Output

 1  2  3  4  5 
 2  4  6  8 10 
 3  6  9 12 15 
 4  8 12 16 20 
 5 10 15 20 25

Example 6.5.3 - Explanation

1. Outer Loop (for i in range(1, 6):)

   • This loop iterates through the numbers 1 to 5. The variable i represents the current row in the multiplication table.
   • range(1, 6) generates the sequence [1, 2, 3, 4, 5]. The outer loop runs 5 times, once for each number in this range.

2. Inner Loop (for j in range(1, 6):)

   • Inside the outer loop, there's another loop that iterates through the numbers 1 to 5. The variable j represents the current column in the multiplication table.
   • range(1, 6) generates the sequence [1, 2, 3, 4, 5]. The inner loop also runs 5 times for each number in this range.

3. Multiplication and Printing (print(f"{i * j:2}", end=' '))

   • Inside the inner loop, i * j calculates the product of the current row number (i) and the current column number (j).
   • The print function is used to display this product. The format string f"{i * j:2}" ensures that the output is at least 2 characters wide, which helps to align the numbers neatly in columns.
   • end=' ' specifies that the output should end with a space instead of a newline, so the numbers are printed on the same line.

4. New Line (print())

   • After the inner loop completes (i.e., after all columns for the current row are printed), print() is called without any arguments to print a newline character. This moves the cursor to the next line, preparing for the next row of the multiplication table.

This results in a complete multiplication table for numbers 1 through 5, neatly formatted in rows and columns.

Example 6.5.3 - Visualisation or visualize this code here.

• First iteration of the outer loop (i = 1):
  • Inner loop runs with j taking values 1 through 5:
    • 1 * 1 = 1
    • 1 * 2 = 2
    • 1 * 3 = 3
    • 1 * 4 = 4
    • 1 * 5 = 5
  • Prints: 1 2 3 4 5 and then a newline.

• Second iteration of the outer loop (i = 2):
  • Inner loop runs with j taking values 1 through 5:
    • 2 * 1 = 2
    • 2 * 2 = 4
    • 2 * 3 = 6
    • 2 * 4 = 8
    • 2 * 5 = 10
  • Prints: 2 4 6 8 10 and then a newline.

• Third iteration of the outer loop (i = 3):
  • Inner loop runs with j taking values 1 through 5:
    • 3 * 1 = 3
    • 3 * 2 = 6
    • 3 * 3 = 9
    • 3 * 4 = 12
    • 3 * 5 = 15
  • Prints: 3 6 9 12 15 and then a newline.

• Fourth iteration of the outer loop (i = 4):
  • Inner loop runs with j taking values 1 through 5:
    • 4 * 1 = 4
    • 4 * 2 = 8
    • 4 * 3 = 12
    • 4 * 4 = 16
    • 4 * 5 = 20
  • Prints: 4 8 12 16 20 and then a newline.

• Fifth iteration of the outer loop (i = 5):
  • Inner loop runs with j taking values 1 through 5:
    • 5 * 1 = 5
    • 5 * 2 = 10
    • 5 * 3 = 15
    • 5 * 4 = 20
    • 5 * 5 = 25
  • Prints: 5 10 15 20 25 and then a newline.

By using nested iterations appropriately, you can solve complex problems that involve multi-dimensional data and perform operations that require comparing or combining elements from different sequences.

Remember that nested loops can significantly increase the complexity of your code and can lead to performance issues if not used carefully. The time complexity of nested loops is typically higher, often resulting in O(n^2), O(n^3), etc., depending on the level of nesting.

Exercise 6.5.1 - Write a Python program to generate a pattern of stars in the shape of a right-angled triangle. The program should ask the user for the number of rows and then print the triangle pattern using nested loops.

For 5 rows, the output should be:

*
**
***
****
*****

_{Exercise 6.5.1 - Model Answer - Make sure to work out the exercise before checking the model answer.}