List all anagrams of a given word
The English Anagram is Greek in origin, being composed of the roots Ana and Gramma; a formation that, according to Thayer’s Greek Lexicon, joins a preposition for “repetition, renewal” and “into the midst… among, between”, with a word meaning “that which has been written”.
Anagrams and words are fixed-length strings that share an equal length and set of characters; moreover, anagrams are composed of unique sequences combining one of every characters from a given word.
The number of possible anagrams of a word is always known. Given a string with length n, an anagrammatizing algorithm computes n! unique strings, including that string, as unique combinations of those n characters.
Finally, while words frequently contain repeated characters, our algorithm need not be concerned with how duplicates are ordered in the anagrams (such that a¹a² a³ would not be equivalent to a²a¹a³ in the anagrams of anagram).
At this point we have assembled enough of a foundation to compose an algorithm that will satisfy our prompt. We know there are a finite number of anagrams for any given word — this being so, we can produce random sequences of those characters until we find all possible combinations.
And our anagrammatizing algorithm, utilizing a Fisher–Yates shuffle:
Invoking allAnagrams initiates the following programmatic sequence:
- The length of word is assigned to len, and anagrams is instantiated as an empty array.
- A loop is initiated that will continue running while the length of anagrams is less than the factorial of len; once this loop concludes, anagrams will be returned.
- Within the loop, anagram results from splitting word into an ordered set of characters, while a counter i is assigned the value of len.
- A second loop is initiated that will continue running while i evaluates to true (i.e. is greater than zero).
- Within the nested loop, r is assigned the value of a random integer in the range of zero to i, and i is decremented.
- A variable tmp is assigned whatever character now occupies position i within anagram.
- The element at index i within anagram is reassigned to whatever character now occupies position r, while the element at index r is reassigned to whatever character was stored as tmp, effectively swapping the elements of anagram at the indices of i and r.
- Once the nested loop concludes, anagram will represent a shuffled order of the characters contained in word; the elements of anagram are then joined to form a string.
- Finally, a conditional evaluates to true if the resulting anagram is not already contained within the set of anagrams; only unique strings are pushed to the collection.
This algorithm approximates our understanding of anagrams and services an accurate response; however, it does so neither efficiently nor with consideration for the complexity of its operation. Given a word containing three characters, the above returns six anagrams — as expected — but may complete an indeterminable number of operations en route to obtaining this result.
In a best-case analysis, the outer while loop in this algorithm will complete a minimum of n! cycles for a problem size of n. In a worst-case analysis, the algorithm may never cease, since it is conceivable that truly randomized permutations may never include all possible anagrams of a given word (however unlikely in practice, since at the time of this writing computers are yet incapable of generating truly random number sequences).
Let’s examine a much cleaner, more efficient means of solving this problem, using recursion to produce exactly the output we seek, with no need for shuffling or randomization.
In a manner similar to how factorials are computed in the above examples, an algorithm which repeatedly invokes itself may be described that will generate all permutations of this problem set.
This tree diagrams all anagrams for “word” starting with the first letter, “w”:
At the onset, there exist four options for beginning any anagram of “word”: one of either “w”, “o”, “r”, or “d”. Subsequent choices are limited to one of three remaining characters, then two, until only one remains to be appended to each string. The process is identical for computing a factorial; starting with a multiplicand, deriving its product by one less its value, and one less again until the multiplier diminishes to zero.
While the following algorithm is more complex, it should appear familiar to our brute force approach:
The above algorithm utilizes a reducing function to accomplish the following programmatic sequence:
- The function invocation is begun with a conditional to verify the truthiness of word. Should word evaluate to false, the function will return one element — an empty string — inside an array.
- If the given word is valid, a reducing function is invoked that iterates through every character of word, returning an array containing all its anagrams.
- Within the reducing function, remainder is assigned to the result of a recursive invocation of allAnagrams, accepting as its argument a string of characters from word containing all those following the current char in sequence of reduction. (i.e. for “w”, the first char of “word”, allAnagrams is invoked with “ord”, then for char “o” of “ord”, “rd” is passed into the next recursion, and so on until the given word evaluates to false.)
- An array containing strings (anagrams) is returned by each recursive call to allAnagrams. The algorithm proceeds to prefix every element returned in this collection with the current char. A conditional ensures no duplicated strings are pushed to the array.
Clarification of the above rests on understanding that which is returned by a recursive function is more significant than how each iteration is invoked; thinking about how each function call will cascade outwards, rather than focusing on what values are passed inward, aids in comprehending the recursive branching structure.
Knowing this, we can describe the state of operations when this algorithm is resolved; on line 6 of the above example, when remainder has assumed the value of an empty string contained in an array.
At any time, we may deduce the values of char, i, and anagrams in the call stack (where each recursive invocation exists within a separate execution context).
In our example, when the function allAnagrams is passed an empty string in the final recursive iteration, the value of remainder within the enclosing scope (where word = ‘d’) will be an empty string contained in an array. At this point the algorithm operates on the elements of remainder, prefixing each one with the value of char (as in the following excerpted code block):
The function prefixes each element rest within remainder with the value of char, pushing the result to the array of anagrams returned by the reducing function. When this for loop concludes, the resulting array is returned into the enclosing scope, which performs the same sequence of actions.
What is important to remember about our algortithm is that while recursive invocations of allAnagrams are made for each element in the array obtained from word, the result of each of these are pushed to the same array of anagrams that is finally returned.