Programming with Python

Stefan Güttel, guettel.com

Exercises: Modules

Problem 1. Write a module with three functions:

  • has_prime_perm(n) that returns True if any permutation of n's digits form a prime number, and
  • has_only_prime_perms(n) that returns True if all of the permutations of n's digits form prime numbers, and
  • prime_perms(n) that returns either a list or a generator of all the prime numbers that can be formed by permuting the digits of n.

Negative numbers have no prime permutations.

Make sure that it is possible to run the module as an ordinary program, in which case it should load n and print the return values of all three functions.

The module may contain other functions.

Hint: Use itertools module to find all the permutations of a number's digits.

Problem 2. Write a program to detect an average number of swaps of the selection sort of a list of length n with a given sample size with and without repeating elements.

Hint: Computing the actual average number of swaps would require generating and sorting lists of all possible orderings, which is $n^n$ lists with not necessarily distinct elements and $n! = n (n-1) \cdots 1$ lists with distinct elements. Even for a length as small as $n = 10$, we would have to generate and sort $10^{10}$ lists.

Instead, load another number, let us call it sample_size, and the do the following:

  1. Generate sample_size random lists with elements from $\{0,1,\dots,n-1\}$. This will allow element repetitions, since you will do no checks to avoid that. Sort the lists, counting the swaps.
  2. Start with some list, say list(range(n)), permute it randomly sample_size times (which will produce lists with only distinct elements), and then sort the obtained permutations, counting the swaps.

Functions for both purposes can be found in random module.

Problem 3. Write a program that loads a text, line by line, until it loads an empty line. It then prints how many Python keywords were in it. You may assume that all the words are separated by one or more spaces.

Hint: The only new issue here is how to recognize a Python keyword. Luckily, there is a standard Python module for that, and it can be found in this list.

Problem 3a. Print how many times each of the keywords has appeared.

Hint: Use a dictionary.