Comparing Recursion and Looping Top Footnotes Contents

Two-dimensional Arrays

Matrices, commonly used in mathematics, are easily represented by two-dimensional arrays in Python. A two-dimensional array is an array whose elements are arrays themselves50. Matrices, like tables (the ones that contain data, not the dining room kind), can be divided into rows and columns. A matrix with p rows and q columns is said to be an p x q matrix. First, we delve into creating matrices and then we will study using them to solve some problems.

Creating a matrix

To make a 3x3 matrix m, one starts by making an array that is 3 elements long. One could simply specify the array directly:

    m = [None,None,None]    #attempt 1

Note we have initialized the array so that each slot in the array holds the value None. This approach works fine if the size of the array is small and known in advance. In other cases, we can use a Python trick to quickly construct an array of a given size:

    m = [None] * 3          #attempt 2

We have hardwired the 3 in the above code fragment, but we could use a variable instead, unlike the first attempt. In fact, we use this trick to define a general-purpose function that makes an array of a given size:

    def createArray(size):
        return [None] * size

    m = createArray(3)          # attempt 3

We designate this initial array as the backbone of the matrix. Pictorially, m looks like this:

The next step is to assign each slot in the backbone to point to an array of size 3:

    m = createArray(3)          #attempt 4

    m[0] = createArray(3)
    m[1] = createArray(3)
    m[2] = createArray(3)

Now m looks like this:

Of course, creating the matrix this way requires we know the size in advance. If we do not, we can use a loop to set the slots of the backbone:

    size = 3

    m = createArray(size)           #attempt 5

    for i in range(0,size,1):
        m[i] = createArray(size)

This code works great if the matrix is square (i.e. the number of rows equals the number of columns). If not, we replace size in the code above with explicit values for the number of rows and the number of columns:

    rows = 3
    cols = 4

    m = createArray(rows)           #attempt 6

    for i in range(0,rows,1):
        m[i] = createArray(cols)

We can see from this code that the length of the backbone corresponds to the number of rows while the length of the arrays to which the backbone slots point represents the number of columns51. Wrapping this code in function that creates a matrix with a given number of rows and columns yields:

    def createMatrix(rows,cols):
        m = createArray(rows)
        for i in range(rows):
            m[i] = createArray(cols)
        return m

Retrieving and modifying values in a matrix

To retrieve a value at row r and column c from a matrix m, one uses an expression similar to:

    value = m[r][c]

One can set the value of the element at row r and column c with an expression similar to:

    m[r][c] = value

Because matrices are built from arrays, the first row has index 0 and the first column has index 0 as well. Thus the first value in the first row in matrix m can be found at:

    m[0][0]

Where is the last element in the last row found in a matrix m with x rows and y columns? Highlight the following line to see the answers:

[       m[x-1][y-1]      ]

Working with matrices

Matrices are typically processed with with two nested for loops. The outer loop runs over the rows, while the inner loop runs over the columns of each row. Here is a generic function for working with a matrix:

    def processMatrix(m):
        rows = len(m)
        cols = len(m[0])

        for r in range(0,rows,1):
            for c in range(0,cols,1):
                # do something with m[r][c]

        return

Note how we retrieve the number of rows by determining the length of the backbone and the number of columns be determining the length of one of the rows.

One useful thing to do with a matrix is visualize it. In other words, we might wish to print out its contents. Using the general purpose template processMatrix as a guide, we simply substitute a print statement for the processing comment:

    def displayMatrix(m):
        rows = len(m)
        cols = len(m[0])

        for r in range(0,rows,1):
            for c in range(0,cols,1):
                print(m[r][c])

        return

If we were to print this matrix:

1 2 3
4 5 6

we would see this output:

    1
    2
    3
    4
    5
    6

The good news is we printed every element as desired. The bad news is our output looks nothing like a matrix; every element is printed on a line by itself. We can fix this problem by using the end directive in our print statement:

    print(m[r][c],end=" ")

Recall that setting the end character to a space will convert all the newlines into spaces. Our output becomes:

    1 2 3 4 5 6

Better, but we need a newline after each row is printed. The easiest way to do this is to print the newline after the inner loop completes:

    def displayMatrix(m):
        rows = len(m)
        cols = len(m[0])

        for r in range(0,rows,1):
            for c in range(0,cols,1):
                print(m[r][c],end="")
            print()

        return

Now our output becomes:

    1 2 3
    4 5 6

which is a reasonable approximation to the way a matrix is supposed to look.

Reading a 2D array from a file

Reading a 2-dimensional array from a file is similar to reading a simple array. As a reminder, here is a function for doing just that:

    def readArrayOfIntegers(fileName):
        array = []
        s = Scanner(fileName)
        value = s.readint()
        while (value != ""):
            array.append(value)
            value = s.readint()
        s.close()
        return array

This function creates an array, grows it using append, and then returns the final version of the array. If the array already exists, things become much simpler; one can read into the array by using a variation of the counting pattern:

    def readArrayOfIntegers2(array,fileName):
        s = Scanner(fileName)
        for i in range(0,len(array),1):
            array[i] = s.readint()
        s.close()
        return # procedure pattern, return value not needed

This second version assumes there is enough data in the file to fill the array. A read error would be generated otherwise. Note that a function that fills a previously constructed array does not require a return value, since the data read from the file is stored in the given array.

If a matrix already exists, then a reading function very similar to readArrayOfIntegers2 is easily written by replacing the single loop with two nested loops:

    def readMatrixOfIntegers(matrix,fileName):
        s = Scanner(fileName)
        for r in range(0,len(matrix),1): # loop over rows
            for c in range(0,len(matrix[0]),1): # loop over columns
                matrix[r][c] = s.readint()
        s.close()
        return

As a final note, use of the scanner means that the data in the input file does not need to be organized in matrix form; all the matrix elements could be on a single line, for example.

2D patterns

Matrix patterns are very similar to patterns that loop over simple arrays. For example, here is a filtered-count implementation for a simple array:

    def countEvens(items):
        count = 0
        for i in range(0,len(items),1):
            if (isEven(items[i])):
                count += 1
        return count

The analogous function for 2D arrays is similar:

    def countEvens2D(matrix):
        rows = len(matrix)
        cols = len(matrix[0])
        count = 0
        for r in range(0,rows,1):
            for c in range(0,cols,1):
                if (isEven(matrix[r][c])):
                    count += 1
        return count

Indeed, most of the patterns for 2D arrays follow directly from the simple array versions. Here is an instance of the extreme pattern:

    def minValue2D(matrix):
        rows = len(matrix)
        cols = len(matrix[0])
        min = matrix[0][0]
        for r in range(0,rows,1):
            for c in range(0,cols,1):
                if (matrix[r][c] < min):
                    min = matrix[r][c]
        return min

Finding the extreme index is a bit trickier since one needs to save two indices, the row and the column of the extreme value:

    def minValueIndex2D(matrix):
        rows = len(matrix)
        cols = len(matrix[0])
        minRow = 0
        minCol = 0
        for r in range(0,rows,1):
            for c in range(0,cols,1):
                if (matrix[r][c] < matrix[minRow][minCol]):
                    minRow = r
                    minCol = c
        return minRow,MinCol

One can return from the innermost loop, if one knows what one is doing:

    def find2D(value,matrix):
        rows = len(matrix)
        cols = len(matrix[0])
        for r in range(0,rows,1):
            for c in range(0,cols,1):
                if (matrix[r][c] == value):
                    return True
        return False # this return must be outside the outside loop!

Be careful where you place the return False, though.

Although the above examples are rather simple, things can get complicated. Suppose you wished to return the index of the row with the largest sum.

    def largestRow(matrix):
        rows = len(matrix)
        ilargestSum = 0;
        largestSum = sum(matrix[0]) # sum the 1st row with a helper
        for r in range(1,rows,1):
            s = sum(matrix[r])
            if (s > largestSum):
                ilargestSum = r
                largestSum = s
        return ilargestSum

    def sum(items):
        total = 0
        for i in range(0,len(items),1):
            total += items[i]
        return total

Curiously, the largestRow function does not appear to follow the pattern of other matrix functions; it only has one loop over the rows. However, it calls a helper function from within its loop and that helper function loops over the columns, so we still have our nested loops.

Simulating 2D arrays with simple arrays

Although Python and most other programming languages allow for two-dimensional arrays, some restricted languages do not. If you are programming in such a language and need a two-dimensional array, not to worry; two-dimensional arrays can be faked with simple arrays. The trick is to convert a two-dimensional address (row index and column index) into a one dimensional address (simple index).

Consider this matrix:

0 1 2 3
4 5 6 7
8 9 10 11

Using our second attempt at displaying this matrix, we would have obtained the following output:

    0 1 2 3 4 5 6 7 8 9 10 11

which looks remarkably like a simple, one-dimensional array! In fact, we can think of this output representing a simple array in which the rows of our two-dimensional array have been stored sequentially.

Now consider extracting the 6 from the 2D version. If our matrix was bound to the variable m, the location of the 6 would be:

    m[1][2]

If our simple array version were bound to the variable n, then the 6 can be found at:

    n[6]

since the numbers in the array reflect the indices of the array. It turns out that there is a very simple relationship between the 2D address and the 1D address. Since the rows are laid out sequentially in the 1D case and since the row index in the 2D case is 1, that means there is an entire row preceding the row of interest in the 1D case. Since the rows are 4 columns long, then four elements precede the row of interest. The column of interest has two columns preceding it, so summing the preceding row elements and the preceding column elements yields 6, exactly the address in the the simple array!

In general, the index of a 2D location in a 1D array can be computed by the following function:

   def simple2DIndex(row,col,rowLength):
       return row * rowLength + col

Note that this function must know the length of each row in order to make its computation. Note also that the row length is simply the number of columns. If we wished to display a 1D simulation of a 2D array, our display function might look like this:

    def displaySimpleMatrix(n,cols):
        rows = len(n) / cols;

        for r in range(0,rows,1):
            for c in range(0,cols,1):
                print(n[simple2DIndex(r,c)])
            print()

        return

In general, when simulating a 2D array, one replaces all indexing of the form:

    m[j][k]

with

   m[j * cols + k]

Ragged 2D arrays

TBW

Problems

lusth@cs.ua.edu


Comparing Recursion and Looping Top Footnotes Contents