Logo Questions Linux Laravel Mysql Ubuntu Git Menu

Algorithm for finding amount of word anagrams?

So I know the theory behind finding anagrams, shown here. For my purposes I need to find the amount of anagrams that can be found from a word excluding duplicates.

Allowing for duplicates, this is fairly simple. aab has the following anagrams:


This amount can be found by calculating the factorial from the amount of letters

factorial := 1

for i := len(word); i > 0; i-- {
    factorial = i * factorial

// aab -> 6

However, if you want to exclude duplicates you have reduced your potential anagrams from 6 to 3. An example of this is the word hello, which has 120 combinations, yet only 60 without duplicates.

I coded my own algorithm that made a map of letters and returned the length of the map, but this had issues as well.

hello -> 24 (actually 60)
helllo -> 24 (actually 120)

How can I accomplish this?

like image 415
Jake D Avatar asked Mar 01 '23 12:03

Jake D

1 Answers

If the validity of the words is not considered whatsoever, then probably best to ditch the word "anagram". You're simply asking about permutations. There is a formula for permutations that accounts for duplicates:

For a word of length n, take the base number of permutations, which is n!. Then, for each unique letter in the word, count the number of occurrences of that letter. For each of those letters, take the factorial of the number of occurences, and divide the number of permutations by it.

For "helllo":

n = 6
h = 1, e = 1, l = 3, o = 1

Permutations = 6! / (1! x 1! x 3! x 1!)
= 720 / 6
= 120
like image 87
Hymns For Disco Avatar answered Mar 05 '23 14:03

Hymns For Disco