Chapter 14

Lists

The sieve of Eratosthenes is an algorithm for making a list of primes that dates back to at least the third century BC:

 List the integers, beginning with 2.

 Circle 2 (it must be prime),

  and cross out all of its multiples. They cannot be prime.

 Circle the next integer that is not yet crossed out (3),

  and cross out its multiples.

 Repeat.

Here is a straight-forward implementation that creates a list of the primes. Recall that the output of the range() function is not itself a list but may be converted to one.

 1 # sieve.py

 2

 3 def sieve(n):

 4 primes = list(range(2, n + 1))

 5 for k in range(2, n + 1):

 6  if k in primes:

 7    for j in range(2 * k, n + 1, k):

 8    if j in primes:

 9     primes.remove(j)

10 return primes

11

12 def main():

13 n = int(input("Enter upper limit: "))

14 print("The primes up to", n, "are:
", sieve(n))

15

16 main()

This program contains nesting that is about as deep as you ever want to go: there is an if inside of a for inside an if inside of a for loop.

Lists

Given our description of the sieve, a list should seem like a natural choice to use for its implementation. You are already somewhat familiar with lists, for two reasons. First, we discussed lists briefly in Chapter 4, and second, lists are very similar to strings.

A Python list stores an ordered sequence of items. But while every item in a string is a single character, list elements may be of any Python type. For example, this list:

 items = [10, False, "hello", 3.14159]

contains an integer, a boolean, a string, and a float. Lists are written inside square brackets. A pair of empty brackets [] denotes the empty list.

Lists Are Like Strings

Lists are stored in memory exactly like strings, except that because some of their objects may be larger than others, they store a reference at each index instead of a single character. A reference in Python is just a memory location that points to where an object is actually stored. (Thus, references are also called pointers.) For example, the list named items given above will be stored in memory something like this:

Each of the individual items in the list is stored somewhere else in memory.

In fact, all Python variables are references, but we have ignored that detail to keep things simpler.

Because lists and strings share this similar structure, the following operations all work the same for lists as they do for strings:

• Indexing using []
• Slicing using [i:j:k] (including full slice copies)
• Concatenation using +
• Repeated concatenation using * n
• for loops
• Accumulation loops
• in and not in

⇒ Caution: Concatenation only works between objects of the same type. For example,

 items = [1, 4, 7] + "abc"

will cause an error because the type of [1, 4, 7] (list) doesn’t match the type of "abc" (string).

Several other built-in functions are available for both lists and strings:

Finally, recall from Chapter 4 that there is a type conversion function for lists:

Lists Are Also Not Like Strings

These operations work with lists but not strings:

Except for sum(), these all modify the original list.

⇒ Caution: Never modify a list that is driving a for loop. For example, the loop at line 5 of Listing 14.1 cannot be over the list primes, because that list changes inside the body of the loop.

Random Functions for Lists

The random module includes these functions for lists:

The choice() function also works on strings; the shuffle() function does not.

Objects and Object Methods

There is one more piece of new syntax in Listing 14.1 that is going to take some background explanation. Every data type in Python is what is known as an object data type, and in order to understand some of the functionality of Python lists (and strings), we need to begin to use object terminology.

For our purposes, an object data type is one that not only describes how data will be stored and what operations can be done with it; it also provides additional functionality via methods, which are specialized functions that you can ask the object itself to perform. Programming that focuses on using object data types is referred to as object-oriented. The programming you have done to this point without thinking in terms of objects is usually called imperative or procedural.

Method Calls

The syntax to call a method from an object is called dot notation:

<object>.<method>(<arguments>)

Compare this with the syntax for a function call in Chapter 3. The differences are that you must ask a particular object to perform a method, and there is a dot (period) between the object and the name of the method. Calling the same method from different objects will usually produce different results.

List Methods

If items is a list object, these are some of the methods that may be called on it:

The remove() method raises an exception if the requested item is not in the list. Exceptions are a Python mechanism for handling errors; for now, we will just try to avoid them.

⇒ Caution: These methods all modify the list they are called on, and only .pop() returns anything. All others return the Python object None, which is returned by any function that does not specify a return value.

Exercises

1. 14.1 Describe how to spot method calls in Python code.
2. 14.2 Perform the sieve on paper for integers up to 100. Give the resulting list of primes.
3. 14.3 Trace the execution of sieve(10) for k = 2 and k = 3. Show the values of j and the contents of the list primes at the end of each execution of the k-loop.
4. 14.4 Use Listing 14.1 to answer these questions:
   1. (a) Identify the method call, along with the name of the object, the name of the method, and any arguments.
   2. (b) Explain why n + 1 is used in three places inside the sieve() function instead of n.
   3. (c) It looks as if lines 5 and 6 could be combined into one statement more efficiently as “for k in primes:”. Does this change work? Explain why or why not.
   4. (d) Explain the role of the step size k in line 7.
   5. (e) Explain the need for the if statement in line 8.
5. 14.5 Explain why the k loop in the sieve() function could stop at $k=\sqrt{n}$ instead of k = n and still work correctly. Modify Listing 14.1 to reflect this improvement. You may want to use the ceil() function from the math module.
6. 14.6 Explain why the j loop in the sieve() function could start at j = k2 instead of j = 2k, and still work correctly. Modify Listing 14.1 to reflect this improvement.
7. 14.7 Write a function randints(n, a, b) that returns a list of n random integers between a and b (inclusive). The integers do not need to be distinct. Use a list accumulator to build the list. Write a main() to test your function.
8. 14.8 Write a function randintsdistinct(n, a, b) that returns a list of n distinct random integers between a and b (inclusive). Write a main() to test your function.
9. 14.9 Write a function randfloats(n, a, b) that returns a list of n random floats from the interval [a, b]. Write a main() to test your function.
10. 14.10 Write a mysum(items) function that returns the sum of the elements in the list items without using the built-in sum() function. Test your function on random lists against the built-in function.
11. 14.11 Write a mymin(items) function that returns the smallest item in the list items without using the built-in min() function. Test your function on a random list of numbers, a list of strings, and a string.
12. 14.12 Write a mymax(items) function that returns the largest item in the list items without using the built-in max() function. Test your function on a random list of numbers, a list of strings, and a string.
13. 14.13 Write a mean(items) function that returns the average of the values in the list items. Assume all entries are numeric. Test your function on random lists.
14. 14.14 Write a median(items) function that returns the median of the values in the list items. Look up the definition of median if you need it, and test your function on random lists. Do not modify the original list; instead, make a copy of the list before sorting it. Test your function on random lists.
15. 14.15 Write a evens(items) function that returns a new list of only the even integers in the list items. Test your function on random lists.
16. 14.16 Write a odds(items) function that returns a new list of only the odd integers in the list items. Test your function on random lists.
17. 14.17 Write a block(names, blocked) function that returns a new list of only the names in the list names that are not in the list blocked. Write a main() to test your function.
18. 14.18 Write a mychoice(items) function that returns a random element from the list items without using the choice() function. You may use other functions from the random module. Write a main() to test your function.
19. 14.19 Write a function delrand(items) that deletes and returns one random element from the list items. Write a main() to test your function.
20. 14.20 Improve Exercise 10.6 by modifying the flip() function to randomly return either the string "heads" or the string "tails".
21. 14.21 Use a list to improve the countrolls.py program from Exercise 10.8. Hint: start with a list of 0’s.
22. 14.22 Write a program randmadlib.py that modifies Listing 2.1 to generate random Mad Libs (in correct grammatical form) by choosing random nouns, verbs, adjectives, etc., instead of asking the user for them. Make your own lists of each type of word and create your own sentence template.
23. 14.23 Write a function swap(items, i, j) that swaps the elements items[i] and items[j].
24. 14.24 Write a function myreverse(items) that reverses the list items without using the list method .reverse(). Do not return anything; just change the order of the elements in the given list. Test your function on random lists.
25. 14.25 Write a function myshuffle(items) that shuffles the list items without using the shuffle() function from the random module. This is trickier than it sounds, but here is an algorithm that works, where n is the length of the list:

     for i = 0 to n − 2:

     choose a random j between i and n − 1 (inclusive)

     swap items i and j

    Explain why the for loop does not need to go to n − 1. Write a main() to test your function.

26. 14.26 Write a function issorted(items) that returns True if the list items is sorted in increasing order; otherwise, it should return False. Hint: it is enough to compare each element with the one next to it.
27. 14.27 Write a function mysort(items) that sorts the given list without using the .sort() method. Here is an algorithm that will work:

     Find the smallest element and swap it with item 0.

     Find the next smallest element and swap it with item 1.

     Continue.

    Test your function on known lists and random lists.

28. 14.28 Write a function primefactors(n) that returns a list of the (unique) prime factors of the integer n. For example,

     primefactors(24) = [2, 3]

    Test your function on n = 2 through 100.

29. 14.29 Write a function primefactorization(n) that returns a list that represents a complete factorization of n into primes. For example,

     primefactorization(24) = [2, 2, 2, 3]

    Test your function on n = 2 through 100. Hint: think of repeated use of smallestdivisor().

30. 14.30 Write a function divisors(n) that returns a list of the proper positive divisors of the integer n, including 1 but excluding n itself.
31. 14.31 Write a function isperfect(n) that returns True if n is a perfect number, meaning it is positive and equal to the sum of its proper divisors (see the previous exercise). Use your function to find all perfect numbers less than 10,000.
32. 14.32 The Fibonacci sequence is

    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . .

    defined by beginning with two 1’s and then adding the two previous numbers to get the next one. Write a function fib(n) that returns a list of the first n Fibonacci numbers. How large is the 100th Fibonacci number?