查找单词异序词数量的算法？

Question

我知道找到变位词的理论，可以在这里看到。对于我的目的，我需要找到从一个单词中能够找到的变位词数量不包括重复的。

允许有重复的情况下，这是相当简单的。 aab有以下变位词：

aab
aab
aba
aba
baa
baa

这个值可以通过计算字母数量的 阶乘 得出

factorial := 1

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

// aab -> 6

然而，如果你希望排除重复项，那么可能会将潜在的变位词从6个减少到3个。例如，单词hello有120种组合方式，但是去掉重复后只有60种。

我编写了自己的算法，制作了一个字母映射，并返回了该映射的长度，但这也存在问题。

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

我该如何做到这一点？

- Jake D

---

相信 hello 有60个不重复的字谜。helo 有24个，所以肯定hello更多。 - user3386109

Answer 1

如果不考虑单词的有效性，那么最好放弃“anagram”这个词。你只是在询问排列。有一个排列公式可以解决重复问题:

对于长度为 n 的单词，取排列的基数，即 n!。 然后，对于单词中的每个唯一字母，计算该字母出现的次数。对于这些字母中的每一个，取其出现次数的阶乘，并将排列数除以它。

对于“helllo”:

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

Permutations = 6! / (1! x 1! x 3! x 1!)
= 720 / 6
= 120

- Hymns For Disco

---

运行得非常好！你从哪里得到这个算法的？ - CyanCoding

@CyanCoding 我最初是在高中的概率课上学习了它。 - Hymns For Disco

Answer 2

代码：

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

}

结果：

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

- pullidea-dev

Answer 3

您可以使用一些组合数学。首先，您要计算每个字符出现的次数。然后使用牛顿符号将每个字符放在其位置上。例如给定单词

aabcdee 您有7个位置可以放置单个字母，并且您有重复项-双倍的a和双倍的e。
所以您使用以下公式
您可以将a放置在7个位置中的2个位置，然后将其乘以可以放置b的位置数量-剩余5个位置中的1个位置。然后将c放置在4个位置中的1个位置。然后将d放置在3个位置中的1个位置。然后将e放置在2个位置中的2个位置。
将每个公式相乘将为您提供线性时间内的排列数（如果使用哈希映射进行字母计数）。

- JRazek