Anagrams Part 3 – Using a Map

So how can we speed up our anagram algorithm? Well, how about we rearrange the input word list so that it stores all anagrams for us? This would be a one-off operation at the start of the program. From then on we would simply find all anagrams with a simple look up operation.

Hmmm how can we do that?

Well all anagrams of a particular word are made up of the same letters. If we sort all the anagrams into lexicographical order we get the same ordered sequence of characters. For example the following three words:

part trap rapt

are made up of the sorted sequence aprt. Lets call this the key, and the three original words the values.

What we need is a data structure that can store the key and values like this:

aprt => part trap rapt

This can be represented nicely in C++ as follows:

string => vector<string>

We can use a map to store this:

map<string, vector<string> >

We build the map by reading each word from the word list, sorting it, then adding it to the map and appending the unsorted word to the associated vector. We will end up with an in-memory representation like this:

aprt => part trap rapt
act => act cat
aeprs => spare pares

The code can explain this much better than I can, here is the complete program:

#include <iostream>
#include <hash_map>
#include <vector>
#include <string>
#include <fstream>
#include <algorithm>

using namespace std;
using stdext::hash_map;

typedef vector<string> value_type;
typedef hash_map<string, value_type> Dict;
typedef Dict::const_iterator dict_iter;

int main()
{	
	Dict dict;
	int word_count = 0;
	
	ifstream in_file("words.txt");
	if (!in_file) {
		cerr << "Input file not found" << endl;
		exit(1);
	}
	
	string s, sorted_s;
	// read a word, sort the chars then use it as a key to the hash table. Append the original
	// unsorted word to the vector that is the value.
	while (in_file >> s) {
		sorted_s = s;
		sort(sorted_s.begin(), sorted_s.end());
		dict[sorted_s].push_back(s);
		word_count++;
	}
	
	cout << word_count << " words read" << endl;
	
	string str;
	while (str != "q") {
		cout << "\nEnter letters (q to quit): ";
		cin >> str;
		sort(str.begin(), str.end());
		dict_iter iter = dict.find(str);		// find the sorted string in the hash table
		if (iter != dict.end()) {				// if it exists...
			value_type vec = (*iter).second;	// ...grab the vector 
			cout << vec.size() << (vec.size() == 1 ? " anagram -> " : " anagrams -> ");
			// output the anagrams
			copy (vec.begin(), vec.end(), ostream_iterator<string>(cout, " "));
			cout << endl;
		}
		else 
			if (str != "q") cout << "word not found" << endl;
	}
	return 0;
}

You can see the map is built in only 4 lines of C++ (lines 29 to 32). To keep things interesting I have used a hashmap instead. This is a drop-in replacement for std::map offering potentially better performance. Note that it lives in the stdext namespace if you use Visual Studio.

If you run this program you will find it returns answers instantaneously. Even if you enter a long nonsensical string it will determine that there are no anagrams instantly. In fact, using a hashmap can offer us potentially O(1) performance i.e. constant time. This means the performance does not depend on the length of the input string.

What this teaches us is that it is sometimes beneficial to change the representation of the input data in order to speed up the program. A map (or hashmap) is an extremely efficient way of storing related data. If you think about it we have actually created a database, where each <key, value> pair is a record in the database. The value is the data we require (the anagrams) and the key is the index (the sorted string).

Anagrams Part 2 – Binary Search

One of the problems with the previous algorithm (see Anagrams Part 1) is that it performed a linear search of the word list to find each permutation. That is, if there are 38000 words then the worst case will be 38000 comparisons. And for anagrams most cases will be worst cases. That’s fine if the word list is a random jumble, but most word lists are stored in alphabetical order. That means we can choose a much better search algorithm – the binary search.

Binary search works with sorted data. Imagine if you had a phone book and wanted to find if “Flubberblubber” is in the book. You wouldn’t start at the beginning and scan through to the end would you? No, you’d probably open the book roughly halfway through. You might see that all the names start with “M”. You’d then open the book again roughly halfway between the start and the “M” page. You might hit names that start with “H”. So again you’d open the book halfway to “H”. This time you hit “E”. Now you’d open the book halfway between “E” and “H”. See how you are homing in on the desired “F” pages after only 3 lookups?

In fact, if the phone book contained 1 million numbers you’d get to the desired name (or find it didn’t exist) within 20 lookups if you followed this method! So a worst case of 20 compared to 1,000,000 using linear search. Even better, binary search scales remarkably well. If the phone book contained 1 billion numbers, the number of lookups would only increase to about 30. Now that’s impressive. It should be obvious that the reason this works is that we can discard 50% of the remaining pages of the phone book every time we do a lookup. In fact binary search is an O(log n) algorithm, while linear search is O(n).

So does the C++ Standard Library contain this useful facility? Of course it does! There is a binary_search() function in the <algorithm> header that does exactly what we want.

Simply replace the following lines from the original program:

vector<string>::const_iterator iter = find(dict.begin(), dict.end(), str);
if (iter != dict.end())
    // we have found an anagram so print it
    cout << *iter << " ";

with:

if (binary_search(dict.begin(), dict.end(), str))
    // we have found an anagram so print it
    cout << str << " ";

Not only is it faster it’s also a bit clearer (no iterators). Running the program to find anagrams of integral results in a near instantaneous result, as opposed to 21 secs with linear search.

So is this the best we can do? Not really. Running the program on a 16 character string still takes minutes to return an answer.

We’ve solved the problem of searching but unfortunately we are still generating in the order of n! permutations of the input string. This is now the bottleneck, so in the next part we’ll look at reducing that.

Anagrams Part 1 - Brute Force

Beginner programmers are often surprised when a supposedly simple program takes a lot longer to execute than they expect. After all if a modern PC can simulate an entire battle consisting of hundreds of soldiers in real-time 3D, surely it can display all anagrams of a phrase without pausing to think for hours? Consider the problem of finding all anagrams of a word that are the same length as the word. For example, the word "integral" has 8 characters and has the following 8 character anagrams:

alerting
altering
integral
relating
triangle

For completeness we include the original string in the list of anagrams. I used a word list of around 38,000 common English words to get the anagrams. So how can we program a computer to find these anagrams? A first guess algorithm might be:

for each permutation p of characters in string s
...if p exists in the wordlist then print anagram

Luckily the C++ Standard Library contains a handy function called next_permutation(first, last) that takes a pair of iterators as arguments. The function changes the order of the elements in the range [first, last) to the next lexicographic permutation and returns true. If there is no next_permutation, it arranges the sequence to be the first permutation and returns false. For all permutations to be generated the starting sequence must be initially sorted in ascending order.

So, using this function we can easily generate all permutations of a word and check them against a word list.

Such a program might look like this:

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <algorithm>

using namespace std;

int main() 
{ 
    vector<string> dict;
    int word_count = 0;
    
    // Make sure words.txt is in your current directory.
    // Search the web for a suitable word list.
    ifstream in_file("words.txt");
    if (!in_file) {
        cerr << "word list not found" << endl;
        exit(1);
    }
    // read word list and store words in a vector
    string s;
    while (in_file >> s) {
        dict.push_back(s);
        word_count++;
    }
    
    cout << word_count << " words read" << endl;
    string str;
    while (true) {
        int count = 0;
        cout << "\nEnter letters (q to quit): ";
        cin >> str;
        if (str == "q") break;
        bool perms_remaining = true;
        sort(str.begin(), str.end()); // necessary so that next_permutation finds all permutations
        while (perms_remaining) {
            count++;
            vector<string>::const_iterator iter = find(dict.begin(), dict.end(), str);
            if (iter != dict.end())
                // we have found an anagram so print it
                cout << *iter << " ";
            perms_remaining = next_permutation(str.begin(), str.end());
        }
        cout << endl << count << " permutations" << endl;
    }
}

When I run this on my Core 2 Duo 2.1GHz PC it takes 21 seconds to find all 5 anagrams. There are noticeable pauses between each found word. Adding another letter to the input to make, say, integrals and the time rockets to 3 min 12 sec. So going from 8 characters to 9 characters results in a 9-fold increase in time. Yes folks this is an O(n!) algorithm, one of the worst performing possible.

There are n! permutations if the string has n unique characters, so for n = 8 there are 40320 permutations. For each of these the program scans the word list of 38000 words to find a match. Considering there are only a handful of anagrams for any given word, that means in effect the full list is being scanned every time. That makes 40320*38000 = 1,532,160,000 string comparisons. Now that's brute-force! That's where the 21 seconds goes. And that's for a relatively short word. Surely there must be a better way? Of course there is! See Part 2 to find out.

Cheating at Bookworm Adventures

Bookworm Adventures is a word game where you have to make words out of a grid containing 16 random  letters. The longer the word, the bigger the damage you do to the current baddie. In essence, it's an anagram game - you need to jumble the letters up to make a legal word. I thought it would be fun as a first C++ project to create a program that outputs the longest legal word using the grid letters as input. Of course, me and my 7-year old son would only use this as a last resort (maybe).

This sort of thing can be done in 20 lines of Ruby. And probably any other scripting language. I guarantee my C++ version will be much longer! Still, it's a useful exercise because it will involve I/O streams and STL containers and algorithms. It's also small enough to be done in an evening (hopefully)!