# Construct all unique anagrams of a n-character string

There were other questions regarding checking for anagrams. I want to construct all unique anagrams of a word. I'm not sure as to where it would be applicable but it's fun. I used an algorithm previously, thanks to sanyarem. As he himself points out, the algorithm doesn't generate unique results. SO I was wondering if there is a standard way to do it considering it's a mathematical question in the basic level. I checked out some journals too, but they had recursive functions or n-for loop methods which take a long time.

EDIT: Wow..no one? okay, let me tell you my approach, maybe improvements can be suggested. I'm assigning each character in the string a number. Yes, this kind of restricts the $n < 9$. Then I iterate from the minimum number that can be formed from the assigned numbers. And I iterate until the max. number that can be formed from the same set.

For each iteration, I check if the number at present is a permutation of the key (the original character to number conversion). If it is, then it is an anagram. This way repetitions are avoided too.

Problem: The efficiency is way too low.

-
"which take a long time" is inherent in a process which can generate $n!$ different outputs. –  András Salamon Jun 5 '13 at 16:30
Not necessarily. I'm talking in relative terms, obviously. Who knows, someone might have an interesting take on this. –  SPRajagopal Jun 5 '13 at 17:28
There are many standard ways to do it. I imagine they would be covered by any textbook on enumerative combinatorics, and they're certainly covered by Knuth's Art of Computer Programming vol. 4. –  Peter Taylor Jun 6 '13 at 9:00

I will provide an insight as to why any algorithm can be expected to be "slow", and a recursive algorithm.

We know that the number of anagrams is given by the multinomial coefficient $\displaystyle\binom n {a_1,\ldots,a_k}$, where $n$ is the length of the word, $k$ is the number of distinct letters, and $a_i$ is the number of times the $i$th letter occurs.

Even in the optimistic case that every letter occurs twice, this quantity will still be approximately $2^{-n/2}n!$, which by Stirling's approximation is approximately $\left(\dfrac{n}{\sqrt 2 e}\right)^n$, and so quickly becomes very large once $n \ge 8$.

Nonetheless, let me point out a recursive algorithm which may or may not have a good runtime (I'm not an expert at algorithm design). Let $W$ be our word, with letters $w_i$ of frequency $a_i$. Now:

1. Ensure that the indices and letters are ordered by frequency, i.e. so that $i<j$ implies $a_i \le a_j$, and $W$ starts with the most frequent letter $a_1$ times, then the second most frequent letter, etc.;
2. If all letters of $W$ are the same, return the single anagram, $W$ itself;
3. Otherwise:
• Generate the subsets of $\{1,\ldots,n\}$ of size $a_1$;
• Run the algorithm, starting at step 2, on the word $W'$ obtained by deleting the first $a_1$ letters from $W$ (i.e., removing all letters $w_1$);
• For each of the subsets of size $a_1$ and each anagram of $W'$, riffle them together to an anagram of $W$.
-