Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
How can I calculate the total number of possible anagrams for a set of letters?
For example:
"Math" : 24 possible combinations.
math
maht
mtah
mtha
mhat
mhta
amth
amht
atmh
athm
ahmt
ahtm
tmah
tmha
tamh
tahm
thma
tham
hmat
hmta
hamt
hatm
htma
htam
Total: 24
I generated this by actually generating each combination, one by one, but I want to know the formula for calculating the total possible number of combinations of any group of letters.
Suppose you have word with $n_1$ letters $a_1$, $n_2$ letters $a_2$, $\cdots$, $n_k$ letters $a_k$.
First give each letter unique pair: you have first letter $a_1$, it will be $(a_1,1)$, second $a_1$ will be $(a_1,2)$ ,$\cdots$ ,$n_1$th letter $a_1$ will be $(a_1,n_1)$, first letter $a_2$ will be $(a_2,1)$ etc...
Now you have $(n_1+n_2+\cdots+n_k)!$ possible combinations of pairs.
Next it's easy to get letters combinations from pair combination: note that for each $s$ there is $s!$ combinations of pair $(a_s,i)$, but only one combinations of letters, so finally you have:
$$\frac{(n_1+n_2+\cdots+n_k)!}{n_1!n_2!\cdots n_k!}$$
Possible combinations of letters.
The answer in your specific case of "math" is $4!$ as the other answer states.
Generally the number of anagrams of $n$ distinct letters is $n!$. However, this is not true when letters are repeated. More generally the number of anagrams where letters are allowed to be repeated are given by multinomial coefficients.
Think of it like this:
How many choices do you have for the first letter? Four: $4$_ _ _ _.
For the second? Three: $4\cdot 3$ _ _.
Continue like this and you find there are $4\cdot 3\cdot 2\cdot 1 = 4! = 24$ choices in total. You may wish to read this article on the fundamental counting principle.
Although this is 2.5 years late, I would still like to second the answer from @agha, $$\frac{n!}{n_1!n_2!...n_k!}$$ where $n$ is the number of letters in the word and $n_k$ represents the number of repetitions of a letter in the word. For example, the number of anagrams for the word "rearrange" is $$\frac{9!}{3!2!2!1!1!}$$ as there are 9 letters in the word with 'r' repeated 3 times, 'e' and 'a' repeated twice each, and 'n' and 'g' only used once. The reason this is, is because you are first finding all the ways you can rearrange all the letters, just knowing the amount of letters you have. But then in order to remove the duplicates, you have to divide by all the ways you can rearrange all the same letter, i.e. you can technically arrange $\{a, a, a\}$ in $3!$ ways even though it looks the same every time (which is why you want to get rid of these cases).
In your could solution, I would like to suggest a change to remove duplicates these from your list.
var retAnagrams = [];
var add = true;
for (var j = 0; j < anagrams.length; j++)
{
for (var k = 0; k < retAnagrams.length; k++)
if (retAnagrams[k] == anagrams[j])
{
add = false;
break;
}
if (add)
retAnagrams.push(anagrams[j]);
else
add = true;
}
return retAnagrams;
Add this code after the for loop in the else statement of your generateAnagrams(var) function.
I worked out a formula for calculating the number of anagrams for an a-letter word where b letters occur c times, d letters occur e times, f letters occur g times, etc.
a!/((c!^b) * (e!^d) * (g!^f)...)
$n!$, that is factorial of $n$, where $n$ is the number of digits.
If $n=4$, then $4! = 1\times 2\times 3\times 4$
$n! = 1\times 2\times 3\dots\times n$
