Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
"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
1  
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
add comment

1 Answer 1

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$.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.