Nested loops and pattern printing

A loop’s block can contain another loop. The inner loop then runs from start to finish on every pass of the outer one. That is how programs walk through anything with rows and columns, such as seats in a hall, cells of a table or pixels of an image, and it is the idea behind star and number patterns, a classic way to practise loop control.

How nested loops run

This program labels the seats of a small hall with three rows of four seats, and counts how often the inner block runs:

runs = 0
for row in "ABC":
    labels = []
    for seat in range(1, 5):
        labels.append(row + str(seat))
        runs += 1
    print(" ".join(labels))
print("The inner block ran", runs, "times: 3 rows x 4 seats")

runs = 0
for row in range(1, 5):
    for seat in range(row):
        runs += 1
print("A triangle of 4 rows runs it", runs, "times: 1 + 2 + 3 + 4")

A1 A2 A3 A4
B1 B2 B3 B4
C1 C2 C3 C4
The inner block ran 12 times: 3 rows x 4 seats
A triangle of 4 rows runs it 10 times: 1 + 2 + 3 + 4

The outer loop takes "A", and the inner loop goes through seats 1 to 4. Only then does the outer loop move on to "B", and the inner loop starts again from seat 1. So the inner block runs 3 × 4 = 12 times: the number of runs is the product of the two loop sizes. With 1,000 rows of 1,000 items, that is a million runs, which is worth knowing before you nest loops over large data.

When the inner loop’s size depends on the outer variable, add up the sizes instead. In the triangle at the end of the program, row 1 has one pass, row 2 two, and so on, so 4 rows make 1 + 2 + 3 + 4 = 10 runs; n rows make n × (n + 1) ÷ 2.

One string per row

Patterns made of characters are printed one row at a time. The direct way uses an inner loop that prints one star at a time, with end="" so that print() does not start a new line after each star:

n = 4

for i in range(1, n + 1):
    for j in range(i):
        print("*", end="")
    print()

for i in range(1, n + 1):
    print("*" * i)

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

Both halves print the same triangle. In the second, "*" * i repeats the star i times and does the inner loop’s job in one expression. Building the row as a string first and printing it once is shorter, and it is easier to check, because the whole row is one value you can look at. For rows made of several parts, collect them in a list and join them: " ".join(["1", "2", "3"]) gives "1 2 3".

Work out row i first

A reliable way to write any pattern is to describe row i with a formula before writing a loop. For a pyramid of n = 4 rows, count the spaces before the stars and the stars on each row:

The spaces go down by one per row and the stars go up by two, so row i has n - i spaces and 2 * i - 1 stars. With the formula, every variant is a different range():

n = 4

print("Pyramid")
for i in range(1, n + 1):
    print(" " * (n - i) + "*" * (2 * i - 1))

print("Inverted")
for i in range(n, 0, -1):
    print(" " * (n - i) + "*" * (2 * i - 1))

print("Diamond")
for i in range(1, n + 1):
    print(" " * (n - i) + "*" * (2 * i - 1))
for i in range(n - 1, 0, -1):
    print(" " * (n - i) + "*" * (2 * i - 1))

Pyramid
   *
  ***
 *****
*******
Inverted
*******
 *****
  ***
   *
Diamond
   *
  ***
 *****
*******
 *****
  ***
   *

The inverted pyramid uses the same formula with i counting down, range(n, 0, -1). The diamond is the pyramid followed by the inverted pyramid without its first row, range(n - 1, 0, -1), so that the widest row is printed only once. The left padding is all that centres a row: nothing is printed after the stars.

Number patterns: Floyd’s and Pascal’s triangles

Number patterns follow the same plan, with the numbers worked out in the inner loop:

import math

n = 5

print("Floyd's triangle")
number = 1
for row in range(1, n + 1):
    cells = []
    for _ in range(row):
        cells.append(str(number))
        number += 1
    print(" ".join(cells))

print("Pascal's triangle")
row = [1]
differences = 0
for i in range(n):
    texts = []
    for value in row:
        texts.append(str(value))
    print(" " * (n - 1 - i) + " ".join(texts))
    for k in range(len(row)):
        if row[k] != math.comb(i, k):
            differences += 1
    next_row = [1]
    for k in range(1, len(row)):
        next_row.append(row[k - 1] + row[k])
    next_row.append(1)
    row = next_row
print("Numbers that differ from math.comb(i, k):", differences)

Floyd's triangle
1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
Pascal's triangle
    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1
Numbers that differ from math.comb(i, k): 0

Floyd’s triangle puts the counting numbers into rows of 1, 2, 3 … numbers. The counter number is created before both loops, so it keeps counting from one row to the next. The inner loop’s variable is never used, so it has the conventional name _.

Pascal’s triangle starts with a row holding a single 1. Each new row begins and ends with 1, and each number in between is the sum of the two numbers above it, row[k - 1] + row[k]. The numbers are the binomial coefficients, so the program compares every one of them with math.comb(i, k), the standard library’s count of the ways to choose k of i items, and finds no difference. The rows line up only while every number has one digit: the sixth row, 1 5 10 10 5 1, would be wider than the spacing allows.

Tables with aligned columns

Numbers of different widths make ragged columns. str.rjust(width) pads a string with spaces on the left up to width characters, so every column ends in the same place; ljust() pads on the right and center() on both sides.

size = 6
cell = len(str(size * size)) + 1  # the widest product and a space
label = len(str(size))  # the widest row number

line = "x".rjust(label) + " |"
for col in range(1, size + 1):
    line += str(col).rjust(cell)
print(line)
print("-" * len(line))

for row in range(1, size + 1):
    line = str(row).rjust(label) + " |"
    for col in range(1, size + 1):
        line += str(row * col).rjust(cell)
    print(line)

x |  1  2  3  4  5  6
---------------------
1 |  1  2  3  4  5  6
2 |  2  4  6  8 10 12
3 |  3  6  9 12 15 18
4 |  4  8 12 16 20 24
5 |  5 10 15 20 25 30
6 |  6 12 18 24 30 36

The width of a column comes from the widest product, size * size, plus one space to separate the columns, and the row numbers get the width of the largest one, so the grid stays aligned for any size. Each row is built by its inner loop and printed once.

Leaving nested loops early

break leaves only the innermost loop. Searches in a grid often need to stop both loops, and this attempt does not:

hall = ["XX.XX", "X..XX", "XXX.."]   # X is taken, . is free

# Wanted: the first row with two free seats side by side
for r, row in enumerate(hall):
    for s in range(len(row) - 1):
        if row[s] == "." and row[s + 1] == ".":
            print("Found: row", r, "seats", s, "and", s + 1)
            break

Found: row 1 seats 1 and 2
Found: row 2 seats 3 and 4

The goal was the first row with two free seats side by side, but the program reports two rows. The break ended the search in row 1, and then the outer loop simply went on to row 2. There are two clear ways to stop everything:

hall = ["XX.XX", "X..XX", "XXX.."]   # X is taken, . is free


def first_pair(hall):
    for r, row in enumerate(hall):
        for s in range(len(row) - 1):
            if row[s] == "." and row[s + 1] == ".":
                return r, s
    return None


print("With return:", first_pair(hall))

found = None
for r, row in enumerate(hall):
    for s in range(len(row) - 1):
        if row[s] == "." and row[s + 1] == ".":
            found = (r, s)
            break
    if found is not None:
        break
print("With a flag:", found)

With return: (1, 1)
With a flag: (1, 1)

• Return from a function. return ends the function at once, however deeply the loops are nested; returning None after the loops says that nothing was found. This is usually the clearest version.
• A flag. Set a variable when the inner loop finds the answer, and test it in the outer loop to break there too.

The else clause of the inner loop can also tell the outer loop that nothing was found, but code written that way is harder to follow than either version above.

Spaces you cannot see

When a checker compares your output with the expected text, as this lesson’s exercise does, spaces at the end of a row count. print() does not show them, but repr() does:

n = 3
for i in range(1, n + 1):
    print(repr(("*" * (2 * i - 1)).center(2 * n - 1)))

print(repr("*".center(4)), repr("ab".center(5)))

for j in range(1, 4):
    print(j, end=" ")
print("|")

'  *  '
' *** '
'*****'
' *  ' '  ab '
1 2 3 |

center() pads both sides, so every row except the widest ends in spaces. When the padding is an odd number of spaces, one side gets the extra one, and which side depends on the lengths involved: the fourth line of output shows that "*".center(4) puts one space before the star and two after it, while "ab".center(5) puts two before and one after. Printing with end=" " leaves a space after the last number too, just before the |. To get exact rows, build them with left padding only (" " * (n - i) + ...), join the parts with " ".join(), or remove what is left at the end with .rstrip().

Key takeaways

• The inner loop runs completely on every pass of the outer loop; the inner block runs (outer size) × (inner size) times, or the sum of the inner sizes when they change from row to row.
• Build each row as one string, with repetition ("*" * k) or " ".join(parts), and print it once.
• Before coding a pattern, write down the spaces and characters of row i as formulas such as n - i and 2 * i - 1.
• rjust(), ljust() and center() align text; center() and end=" " leave spaces at the ends of rows.
• break leaves only the inner loop: to stop a nested search, return from a function or use a flag.