Algorithms#

Searching for anagrams#

In this notebook we’ll implement algorithms for two tasks:

Testing a pair of words to see if they are anagrams of each other, that is, if you can rearrange the letters in one word to spell the other.
Searching a list of words for all pairs that are anagrams of each other.

There is a point to these examples, which I will explain at the end.

Exercise 1: Write a function that takes two words and returns True if they are anagrams. Test your function with the examples below.

def is_anagram(word1, word2):
    return False

is_anagram('tachymetric', 'mccarthyite') # True

False

is_anagram('post', 'top') # False, letter not present

False

is_anagram('pott', 'top') # False, letter present but not enough copies

False

is_anagram('top', 'post') # False, letters left over at the end

False

is_anagram('topss', 'postt') # False

False

Exercise 2: Use timeit to see how fast your function is for these examples:

%timeit is_anagram('tops', 'spot')

50.8 ns ± 0.779 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

%timeit is_anagram('tachymetric', 'mccarthyite')

49.9 ns ± 3.99 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

How can we compare algorithms running on different computers?

Searching for anagram pairs#

Exercise 3: Write a function that takes a word list and returns a list of all anagram pairs.

short_word_list = ['proudest', 'stop', 'pots', 'tops', 'sprouted']

def all_anagram_pairs(word_list):
    return []

all_anagram_pairs(short_word_list)

[]

The following cell downloads a file containing a list of English words.

from os.path import basename, exists

def download(url):
    filename = basename(url)
    if not exists(filename):
        from urllib.request import urlretrieve
        local, _ = urlretrieve(url, filename)
        print('Downloaded ' + local)
    
download('https://github.com/AllenDowney/DSIRP/raw/main/american-english')

The following function reads a file and returns a set of words (I used a set because after we convert words to lower case, there are some repeats.)

def read_words(filename):
    """Read lines from a file and split them into words."""
    res = set()
    for line in open(filename):
        for word in line.split():
            res.add(word.strip().lower())
    return res

word_list = read_words('american-english')
len(word_list)

Exercise 4: Loop through the word list and print all words that are anagrams of stop.

Now run all_anagram_pairs with the full word_list:

# pairs = all_anagram_pairs(word_list)

Exercise 5: While that’s running, let’s estimate how long it’s going to take.

A better algorithm#

Exercise 6: Write a better algorithm! Hint: make a dictionary. How much faster is your algorithm?

def all_anagram_lists(word_list):
    """Finds all anagrams in a list of words.

    word_list: sequence of strings
    """
    return {}

%time anagram_map = all_anagram_lists(word_list)

CPU times: user 173 ms, sys: 8.02 ms, total: 181 ms
Wall time: 180 ms

len(anagram_map)

Summary#

What is the point of the examples in this notebook?

The different versions of is_anagram show that, when inputs are small, it is hard to say which algorithm will be the fastest. It often depends on details of the implementation. Anyway, the differences tend to be small, so it might not matter much in practice.
The different algorithms we used to search for anagram pairs show that, when inputs are large, we can often tell which algorithm will be fastest. And the difference between a fast algorithm and a slow one can be huge!

Exercises#

Before you work on these exercises, you might want to read the Python Sorting How-To. It uses lambda to define an anonymous function, which you can read about here.

Exercise 7: Make a dictionary like anagram_map that contains only keys that map to a list with more than one element. You can use a for loop to make a new dictionary, or a dictionary comprehension.

Exercise 8: Find the longest word with at least one anagram. Suggestion: use the key argument of sort or sorted (see here).

Exercise 9: Find the largest list of words that are anagrams of each other.

Exercise 10: Write a function that takes an integer word_length and finds the longest list of words with the given length that are anagrams of each other.

Exercise 11: At this point we have a data structure that contains lists of words that are anagrams, but we have not actually enumerated all pairs. Write a function that takes anagram_map and returns a list of all anagram pairs. How many are there?

Data Structures and Information Retrieval in Python

License: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International

Data Structures and Information Retrieval in Python

Algorithms

Contents