Algorithm for finding amount of word anagrams?

Question

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:

aab
aab
aba
aba
baa
baa

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?

Pretty sure `hello` has 60 anagrams excluding duplicates. `helo` has 24, so certainly `hello` has more. — user3386109, Aug 12 '21 at 23:35

Hymns For Disco · Answer 1 · 2021-08-13T00:24:45.220

4

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

edited Aug 13 '21 at 00:24

answered Aug 12 '21 at 23:51

Hymns For Disco

7,530
2
17
33

Works really well! Where'd you get this algorithm from? – CyanCoding Aug 18 '21 at 00:09
@CyanCoding I originally learned it in a high-school class where we were dealing with probability. – Hymns For Disco Aug 18 '21 at 00:31

score 0 · Answer 2 · answered Aug 13 '21 at 03:07

Code:

package main

import (
    "bufio"
    "fmt"
    "os"
    "strings"
)

func main() {

    scanner := bufio.NewScanner(os.Stdin)
    fmt.Print("Enter word: ")
    scanner.Scan()
    word := scanner.Text()

    anagrams := factorial(len(word))
    chars := strings.Split(word, "")
    word1 := word
    n := 0

    for i := 0; i < len(word); i++ {
        n = strings.Count(word1, chars[i])
        if n > 0 {
            anagrams = anagrams / factorial(n)
            word1 = strings.Replace(word1, chars[i], "", -1)
        }
    }

    fmt.Println(anagrams)

}

func factorial(n int) int {

    factorial := 1

    for i := n; i > 0; i-- {
        factorial = i * factorial
    }

    return factorial

}

Results:

aab -> 3
helo -> 24
hello -> 60
helllo -> 120

score 0 · Answer 3 · answered Aug 13 '21 at 09:35

You can use some combinatorics. First you count number of occurrences of each character. Then with newtons symbol you emplace every character on its places. for example given word

aabcdee you have 7 places to put single letter and you have duplicates - double a and double e.
so u use that formula
you can place a on 2 of 7 places then you can multiply it by number of places where u can emplace b - 1 of 5 remaining places. Then c on 1 of 4. Then d on 1 of 3. Then e on 2 of 2.
Multiplying each of these formulas will give you number of anagrams in linear time (in case of using hashmap for letter counting).

Algorithm for finding amount of word anagrams?

3 Answers3