# Anagrams

## 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”.

#### Definition

*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).

#### Brute Force

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.

Using JavaScript’s ES6 syntax, we can derive *n! *for* n*:

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.

#### Recursive

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.

#### Bonus

JavaScript’s arrow function syntax allows us to complete the prompt using only one line of (ridiculous) code: