Algorithms

Click here to run this chapter on Colab

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)
100781

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)
93406

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

Copyright 2021 Allen Downey

License: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International