Arrays (Tuples and Lists) in Python

Learning objectives

Now that we have seen that Euclid’s GCD algorithm offers an enormous improvement of efficiency over a trivial approach, we wonder whether the same will be true for the sieve of Eratosthenes for finding prime numbers.

To refresh our memory, in the core text, we encountered two prime finding algorithms, reproduced below. Both TrivialPrimeFinder() and the more sophisticated SieveOfEratosthenes() find primes by generating an array of boolean (true/false) variables to store whether a given integer is prime. Therefore, to prepare ourselves to implement these algorithms, we will need to learn how Python implements arrays.

TrivialPrimeFinder(n)
    primeBooleans ← array of n + 1 false boolean variables
    for every integer p from 2 to n
        if IsPrime(p) is true
            primeBooleans[p] ← true
    return primeBooleans

IsPrime(p)
    if p < 2
        return false
    for every integer k between 2 and √p
        if k is a divisor of p
            return false
    return true

SieveOfEratosthenes(n)
    primeBooleans ← array of n + 1 true boolean variables
    primeBooleans[0] ← false
    primeBooleans[1] ← false
    for every integer p between 2 and √n
        if primeBooleans[p] = true
            primeBooleans ← CrossOffMultiples(primeBooleans, p)
    return primeBooleans

CrossOffMultiples(primeBooleans, p)
    n ← length(primeBooleans) - 1
    for every multiple k of p (from 2p to n)
        primeBooleans[k] ← false
    return primeBooleans

Code along summary

Setup

Create a new folder called arrays in your python/src directory, and then create a new file within the python/src/arrays folder called main.py, which we will edit in this lesson.

In main.py, add the following starter code.

def main():
    print("Arrays in Python (i.e., tuples and lists).")


if __name__ == "__main__":
    main()

Declaring tuples

Python contains two different ways of representing arrays. The first we have already briefly encountered and is called a tuple. Tuples are useful if we know what values we would like to set them to be. For example, say that we want to place the first five prime numbers into a tuple primes. We can do so using the following code.

def main():
    print("Arrays in Python (i.e., tuples and lists).")
    primes = (2, 3, 5, 9, 11)


if __name__ == "__main__":
    main()

Let’s print our tuple to the console.

def main():
    print("Arrays in Python (i.e., tuples and lists).")
    primes = (2, 3, 5, 9, 11)
    print(primes)

if __name__ == "__main__":
    main()

Tuples are great when the length of the array that we want to represent is short and fixed, and we will use them whenever we want to return multiple variables from a function. For example, recall the double_and_duplicate() function from when we introduced functions.

def double_and_duplicate(x: float) -> tuple[float, float]:
    """
    Double the input variable and return two copies of it.

    Parameters:
    - x (float): an input float

    Returns:
    tuple[float, float]: Two copies of 2 * x.
    """

    return 2 * x, 2 * x

Tuples are immutable

In our ongoing example, say that we come to the horrible conclusion that 9 is not prime. As we will see soon, Python uses 0-based indexing, which means that we can access the fourth element of our tuple by accessing primes[3]. However, if we attempt to run the following code, then we obtain a TypeError telling us that tuples do not support item assignment.

def main():
    print("Arrays in Python (i.e., tuples and lists).")
    primes = (2, 3, 5, 9, 11)
    print(primes)

    primes[3] = 7


if __name__ == "__main__":
    main()

The problem is that tuples are immutable: once we have declared them, we cannot change their individual elements. Furthermore, their length cannot change, so that in this circumstance, when we one day discover that 13 is also prime, we cannot simply append it to primes. As a result, we will usually use tuples only when we know that the data have fixed length and will not change, such as when we are returning multiple values from a function.

From tuples to lists

Most of the time that we work with arrays in this course, we will implement them in Python using lists, which allow us to change individual elements and are better suited to changing data, such as tables of growing prime numbers. We can declare a list in the same way that we declare any other variable, using the variable name, followed by an equals sign, followed by the values inside a pair of square brackets ([]). For example, to declare an empty list called a, we can use the following notation:

empty_list = []

Sometimes, we want an empty list (since we may append values to it later), and sometimes, we want to create a list of some fixed length whose values we will edit later. In the latter case, we can declare a list of n values val by using the notation [val] * n. In the following code, we declare a to be a list containing six integers, all equal to zero.

n = 6
a = [0] * n  # gives 6 default (zero) values

If we want a small list with a known collection of values, then we can set those values manually. Unlike in other languages, the values of a list are not all required to have the same type. For example, consider the following list with values of mixed type.

mixed_list = [1, 3.14, -42, "Hello", True]

Let’s print our arrays to the console. Add the following code to main() and run your code.

def main():
    print("Arrays in Python (i.e., tuples and lists).")

    empty_list = []

    n = 6
    a = [0] * n  # gives 6 default (zero) values

    mixed_list = [1, 3.14, -42, "Hello", True]

    print(empty_list)
    print(a)
    print(mixed_list)

List indexing

In Python, the value of the array a having index i is denoted a[i]. Python is like many modern languages, and the pseudocode that we use throughout this course, in that it uses 0-based indexing. That is, an array having n values has indices ranging between 0 and n – 1. Let’s use these ideas to set the first value of our array a equal to -8; to do so, we use the notation a[0] = -8 as if we were setting any other variable equal to a value. We can print our list again to see its first value change.

def main():
    print("Arrays in Python (i.e., tuples and lists).")

    # some code omitted for clarity

    a[0] = -8 # a is now [-8, 0, 0, 0, 0, 0]

We can even use arithmetic expressions as either the index or the value of a list element, as shown below.

def main():
    # some code omitted for clarity

    a[0] = -8 # a is now [-8, 0, 0, 0, 0, 0]

    i = 3
    k = 4
    a[2*i-4] = (k//2)**4 + 1  # 2*i - 4 = 2

Finally, we can determine the length of a given array by using the built-in function len(). This is helpful in setting the final value of an array a, since we know that the indices of a list a range between 0 and len(a) - 1. We use this idea below to set the final element of a equal to 43.

def main():
    # some code omitted for clarity

    a[0] = -8 # a is now [-8, 0, 0, 0, 0, 0]

    i = 3
    k = 4
    a[2*i-4] = (k//2)**4 + 1  # 2*i - 4 = 2

    a[len(a)-1] = 43

    print(a)

Python also allows for indexing with negative values, where -1 represents the last element, -2 the second-to-last, and so on. This feature provides a convenient way to access elements from the end of the list without explicitly knowing its length. We can use this to simplify the code above.

def main():
    # some code omitted for clarity

    a[0] = -8 # a is now [-8, 0, 0, 0, 0, 0]

    i = 3
    k = 4
    a[2*i-4] = (k//2)**4 + 1  # 2*i - 4 = 2

    a[-1] = 43

    print(a)

Setting an element of an array with index out of bounds

You might wonder what happens if we try to set the value of a list a for an index that is outside of the range from -len(a) to len(a) – 1. When the index is smaller than 0 or larger than len(a) - 1, we will obtain an IndexError when attempting to set an element of an array with such an index because the index is out of bounds. The following two additional lines show examples of setting elements of an array that would lead to such an error.

def main():
    # some code omitted for clarity

    a[len(a)] = 7  # IndexError!
    a[-len(a)-1] = 2  # IndexError!
    print(a)

Writing a function to generate all factorials

As with any other variable, lists can be input parameters to functions, and they can be returned as well.

In a previous code along, we wrote functions for computing n!. Let us consider a function factorial_array() that takes an integer n as input and returns an array fact of length n+1 containing all factorials between 0! and n!; specifically, for any index k of the array, fact[k] is equal to k!. Using what we have learned, we can write this function in the following way.

# factorial_array takes as input an integer n, and it returns a list of length n+1 whose k-th element is k!
def factorial_array(n: int) -> list[int]:
    """
    Generates a list of factorial values from 0! to n!.

    Parameters:
        n (int): A non-negative integer. The highest factorial to compute.

    Returns:
        list[int]: A list of length n+1 where the k-th element is k!.
                   For example, factorial_array(4) returns [1, 1, 2, 6, 24].

    Raises:
        ValueError: If n is negative.
    """
    if n < 0:
        raise ValueError("Error: negative input given to factorial_array().")

    fact = [0] * (n + 1)
    fact[0] = 1

    for k in range(1, n + 1):
        fact[k] = fact[k - 1] * k

    return fact

Let’s update main() in order to call the function that we just wrote.

def main():
    # some code omitted for clarity

    n = 10
    factorials = factorial_array(n)
    print(factorials)

Finding the minimum value of a list

In the main text, we introduced functions for finding the minimum of two integers and the minimum of three integers. Writing infinitely many functions, one for each possible number of input variables, is not a path we want to take. Instead, we would like to take the minimum of an arbitrary number of inputs, which we know is achieved by Python’s built-in min() function.

One way to take the minimum of an arbitrary number of variables is to assume that these variables are stored in a list a. After ensuring that the list is not empty, we can declare a variable m to hold our minimum that is equal to the initial element of a and then range over the remaining elements of a, updating m every time that we encounter an element that is smaller than the current value of m.

def min_integer_array(a: list[int]) -> int:
    """
    Returns the minimum value in a list of integers.

    Parameters:
        a (list[int]): A list of integers.

    Returns:
        int: The minimum value in the list.

    Raises:
        ValueError: If the list is empty.
    """
    if len(a) == 0:
        raise ValueError("Error: empty list given to min_integer_array.")

    m = 0

    # Iterate over list, updating m if we find a smaller value
    for i in range(len(a)):  # i ranges from 0 (inclusive) to len(a) (exclusive)
        if a[i] < m:
            m = a[i]

    return m

Our current implementation of min_integer_array() will work for some arrays. However, let us consider what happens if every integers in a is positive, such as for the list [3, 2, 1]. For this input list, min_integer_array() will declare m to be zero, and as the function ranges over a, it will never find an element a[i] that is smaller than m. As a result, m is never updated, and min_integer_array() will return 0.

def main():
    # some code omitted for clarity

    c = [3, 2, 1]
    print(min_integer_array(c)) # prints 0

One workaround for this bug is to declare m to be equal to a[0], as follows.

def min_integer_array(a: list[int]) -> int:
    """
    Returns the minimum value in a list of integers.

    Parameters:
        a (list[int]): A list of integers.

    Returns:
        int: The minimum value in the list.

    Raises:
        ValueError: If the list is empty.
    """

    if len(a) == 0:
        raise ValueError("Error: empty list given to min_integer_array.")

    m = a[0]

    # Iterate over list, updating m if we find a smaller value
    for i in range(len(a)):  # i ranges from 0 (inclusive) to len(a) (exclusive)
        if a[i] < m:
            m = a[i]

    return m

An alternative approach is to declare m to be equal to zero, but in the for loop, update m either if we are considering the first element or if the current element of a is smaller than m. We can then preserve our ranging over the entire list, and we get to use the or logical operator that we learned about in a previous code along.

def min_integer_array(a: list[int]) -> int:
    """
    Returns the minimum value in a list of integers.

    Parameters:
        a (list[int]): A list of integers.

    Returns:
        int: The minimum value in the list.

    Raises:
        ValueError: If the list is empty.
    """

    if len(a) == 0:
        raise ValueError("Error: empty list given to min_integer_array.")

    m = 0

    # Iterate over list, updating m if we find a smaller value
    for i in range(len(a)):  # i ranges from 0 (inclusive) to len(a) (exclusive)
        if i == 0 or a[i] < m:
            m = a[i]

    return m

Two shorthand ranging tricks

Python offers two convenient shorthand tricks for ranging over arrays that we will apply to our correct implementations of min_integer_array() as an example.

The first trick addresses ranging over all the indices of a list. Rather than needing the lengthy statement for i in range(len(a)), if we have no explicit need for the index i, we can iterate directly over a instead using the line for val in a. We can now directly access each value in a with the variable val (which we can name what we like). We apply this change to min_integer_array() below.

def min_integer_array(a: list[int]) -> int:
    """
    Returns the minimum value in a list of integers.

    Parameters:
        a (list[int]): A list of integers.

    Returns:
        int: The minimum value in the list.

    Raises:
        ValueError: If the list is empty.
    """

    if len(a) == 0:
        raise ValueError("Error: empty list given to min_integer_array.")

    # will store the minimum value
    m = a[0]

    # Iterate over list, and if we find something smaller than m, update m
    for val in a:  # val takes on each value in a
        if val < m:
            m = val

    return m

The second shorthand trick allows us to range over both the indices and the values of a list. If we intend to use both the index (i) and associated value (val) when ranging over a list, we can use the notation for i, val in enumerate(a). Below, we update our other implementation of min_integer_array() to apply this trick.

def min_integer_array(a: list[int]) -> int:
    """
    Returns the minimum value in a list of integers.

    Parameters:
        a (list[int]): A list of integers.

    Returns:
        int: The minimum value in the list.

    Raises:
        ValueError: If the list is empty.
    """

    if len(a) == 0:
        raise ValueError("Error: empty list given to min_integer_array.")

    m = 0

    # Iterate over list, updating m if we find a smaller value
    # i ranges from 0 (inclusive) to len(a) (exclusive) 
    # while val takes on each value in a
    for i, val in enumerate(a):
        if i == 0 or val < m:
            m = val

    return m

Variadic functions

We may also want to find the minimum of an arbitrary collection of input integers without assuming that these integers are contained within an array. For example, Python’s built-in min() function can take an arbitrary number of integers or floats as input. We provide an example of a variadic function, which is one that takes in a variadic argument. A variadic argument can take in an arbitrary number of parameters.

In Python, we utilize the asterisk (*) notation in a function’s parameters to denote a variadic parameter, denoting an arbitrary number of arguments; this notation is commonly referred to as unpacking in Python. The arguments will be stored in the parameter variable as a tuple, which we can then access as needed. The following min_integers() variadic function, for instance, takes an arbitrary number of integers, which we denote by *numbers: int; when the function is called, these integers are then stored in a tuple that we can access named numbers.

As with lists, we can then iterate over the numbers tuple in a similar fashion to how we iterated over the list in the min_integer_array() function in order to find the minimum.

def min_integers(*numbers: int) -> int:
    """
    Returns the minimum value among a variable number of integers.

    Parameters:
        *numbers (int): A variable number of integers.

    Returns:
        int: The minimum value among the provided numbers.

    Raises:
        ValueError: If no numbers are provided.
    """
    if len(numbers) == 0:
        raise ValueError("Error: no numbers given to min_integers().")

    # will store the minimum value
    m = numbers[0]

    # Iterate over tuple, and if we find something smaller than m, update m
    for val in numbers:
        if val < m:
            m = val

    return m

Note how similar min_integers() is to min_integer_array(); the only difference is the inputs that they take. Any time that we see very similar code arising in our work, a red alert should go off in our brains telling us to use a subroutine. This way, we will only have to write (and debug) half as much code.

In this particular case, because we have already implemented min_integer_array(), we can use it as a subroutine in min_integers(). We will say much more about the effective use of subroutines as this course progresses.

The only issue is that technically, because numbers is a tuple, we cannot pass it as input to min_integer_array(). Instead, we need to convert it to a list first. Fortunately, Python contains a built-in list() function that converts a tuple to a list.

def min_integers(*numbers: int) -> int:
    """
    Returns the minimum value among a variable number of integers.

    Parameters:
        *numbers (int): A variable number of integers.

    Returns:
        int: The minimum value among the provided numbers.

    Raises:
        ValueError: If no numbers are provided.
    """

    if len(numbers) == 0:
        raise ValueError("Error: no numbers given to min_integers().")

    return min_integer_array(list(numbers))

Lists are pass by reference

Before we move on to the next code along and implement primes, we make an important point about lists in Python. When we introduced functions in a previous code along, we pointed out that Python uses “pass by value” for certain input parameters. This means that when we pass a variables such as an integer or string into a function, Python creates a copy of that variable and edits the copy, so that the original variable’s value is preserved.

This behavior is different for lists. Consider the following function, which changes the first element of an input list to 1.

def change_first_element(a: list[int]):
    a[0] = 1

When we call this function using the code below, we will see that change_first_element() edits c within the function. As a result, you might like to think about lists as pass by reference, since when we pass a list into a function, we are able to change the underlying data.

def main():
    print("Arrays (aka lists).")

    # ...

    c = [0] * 6  # is equal to [0, 0, 0, 0, 0, 0]

    change_first_element(c)

    print(c)  # prints [1, 0, 0, 0, 0, 0]

Later in the course, we will say more about what is happening when a function takes a list (or any variable) as a parameter. For now, in practice, we will use lists most of the time throughout this course, and we may use the generic term “array” to refer specifically to a Python list unless a tuple is more appropriate.

Looking ahead

We are now ready to return to apply what we have learned about arrays and lists to implement and compare the prime finding algorithms that we introduced in the core text. How fast could the sieve of Eratosthenes be? Join us to find out!

Check your work from the code along

We provide autograders in the window below (or via a direct link) allowing you to check your work for the following functions:

• factorial_array()
• min_integer_array()
• min_integers()

powered by Advanced iFrame

---