Anagram Generation
To top off our conversation, let’s tackle our most complex recursive problem yet. We’re going to use everything we’ve got in our recursion toolbox to make this work.
We’re going to write a function that returns an array of all anagrams of a given string. An anagram is a reordering of all the characters within a string. For example, the anagrams of "abc" are:
| | ["abc", |
| | "acb", |
| | "bac", |
| | "bca", |
| | "cab", |
| | "cba"] |
Now, let’s say we were to collect all the anagrams of the string "abcd". Let’s apply our top-down mindset to this problem.
Presumably, we could say that the subproblem of "abcd" is "abc". The question then is this: if we had a working anagrams function that returned all the anagrams of "abc", how can we use them to produce all the anagrams of "abcd"? Think about this for a bit and see if you can come up with any approaches.
Here’s the approach that occurred to me. (There are others, though.)
If we had all six anagrams of "abc", we can come up with every permutation of "abcd" if we stick the "d" in every possible spot within each anagram of "abc":
Here is a Python implementation of this algorithm. You’ll note that it’s certainly more involved than the previous examples in this chapter:
| | def anagrams_of(string): |
| | if len(string) == 1: |
| | return [string[0]] |
| | |
| | collection = [] |
| | |
| | substring_anagrams = anagrams_of(string[1:]) |
| | |
| | for substring_anagram in substring_anagrams: |
| | for index in range(len(substring_anagram) + 1): |
| | new_string = (substring_anagram[:index] |
| | + string[0] |
| | + substring_anagram[index:]) |
| | collection.append(new_string) |
| | |
| | return collection |
This code is not trivial, so let’s break it down. For now, we’ll skip over the base case.
We start by creating an empty array in which we’ll collect the entire collection of anagrams:
| | collection = [] |
This is the same array we’ll return at the end of our function.
Next, we grab the array of all anagrams from the substring of our string. This substring is the subproblem string—namely, from the second character until the end. For example, if the string is "hello", the substring is "ello":
| | substring_anagrams = anagrams_of(string[1:]) |
Note how we use the top-down mentality to assume that the anagrams_of function already works on the substring.
We then iterate over each of the substring_anagrams:
| | for substring_anagram in substring_anagrams: |
Before moving on, it’s worth noting at this point that we are using a combination of loops and recursion together. Using recursion doesn’t mean that you have to eliminate loops from your code altogether! We’re using each tool in the way that most naturally helps us solve the problem at hand.
For each substring anagram, we iterate over each of its indexes—plus an extra index at the end. For each index, we create a brand new string (called new_string), and fill it with the substring anagram plus the first character of our current string inserted at the current index:
| | for index in range(len(substring_anagram) + 1): |
| | new_string = (substring_anagram[:index] |
| | + string[0] |
| | + substring_anagram[index:]) |
For example, if the string is "abcd" and the substring anagram is "bcd", we iterate over each index (plus an extra index at the end), which comes out to 0 through 3, and create the following new strings:
| | "abcd" # inserted 'a' at index 0 |
| | "bacd" # inserted 'a' at index 1 |
| | "bcad" # inserted 'a' at index 2 |
| | "bcda" # inserted 'a' at index 3 |
Really, the substring anagram "bcd" doesn’t have an index 3, but we iterate through index 3 so we can insert the "a" at the very end of the substring anagram.
Each new_string represents a new anagram, so we add it to our collection:
| | collection.append(new_string) |
When we’re done, we return the collection of anagrams.
The base case is where the substring contains only one character, in which case there’s only one anagram—the character itself!
The Efficiency of Anagram Generation
As an aside, let’s stop for a moment to analyze the efficiency of our anagram-generating algorithm, since we’ll discover something interesting. In fact, the time complexity of generating anagrams is a new category of Big O that we haven’t encountered before.
If we think about how many anagrams we generate, we’ll notice an interesting pattern.
For a string containing three characters, we create permutations that start with each of the three characters. Each permutation then picks its middle character from one of the two remaining characters, and its last character from the last character that’s left. This is 3 * 2 * 1, which is six permutations.
Looking at this for other string lengths, we get:
| | 4 characters: 4 * 3 * 2 * 1 anagrams |
| | 5 characters: 5 * 4 * 3 * 2 * 1 anagrams |
| | 6 characters: 6 * 5 * 4 * 3 * 2 * 1 anagrams |
Do you recognize this pattern? It’s a factorial!
So if the string has six characters, the number of anagrams is whatever the factorial of 6 is. This is 6 * 5 * 4 * 3 * 2 * 1, which computes to 720.
The mathematical symbol for factorial is the exclamation point. So, factorial 6 is expressed as 6!, and the factorial of 10 is expressed as 10!.
Remember that Big O expresses the answer to the key question: if there are N data elements, how many steps will the algorithm take? In our case, N would be the length of the string.
For a string of length N, we produce N! anagrams. In Big O notation then, this is expressed as O(N!). This is also known as factorial time.
O(N!) is the slowest category of Big O we’ll encounter in this book. Let’s see how it looks compared to other “slow’’ Big O categories:
Although O(N!) is extremely slow, we don’t have a better option here, since our task is to generate all the anagrams, and there simply are N! anagrams for an N-character word.
In any case, recursion played a pivotal role in this algorithm, which is an important example of how recursion can be used to solve a complex problem.
