查找单词字谜数量的算法？

Question

所以我知道找到字谜背后的理论，如图所示。出于我的目的，我需要找到可以从单词中找到的字谜数量，排除重复项。

允许重复，这相当简单。 具有以下字谜：aab

aab
aab
aba
aba
baa
baa

这个数量可以通过从字母的数量计算阶乘来找到

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

但是，如果要排除重复项，则可以将潜在的字谜从6个减少到3个。这方面的一个例子是单词 ，它有120个组合，但只有60个没有重复的组合。hello

我编写了自己的算法，该算法制作了字母地图并返回了地图的长度，但这也有问题。

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

我怎样才能做到这一点？

Answer 1

如果这些词的有效性没有得到任何考虑，那么最好放弃“字谜”这个词。你只是在问排列。有一个用于解释重复项的排列公式：对于一个长度的单词，取排列的基数，即 。然后，对于单词中的每个唯一字母，计算该字母的出现次数。对于这些字母中的每一个，取出现次数的阶乘，并将排列数除以它。nn!对于“地狱”：n = 6h = 1, e = 1, l = 3, o = 1Permutations = 6! / (1! x 1! x 3! x 1!)= 720 / 6= 120

Answer 2

法典：package mainimport (&nbsp; &nbsp; "bufio"&nbsp; &nbsp; "fmt"&nbsp; &nbsp; "os"&nbsp; &nbsp; "strings")func main() {&nbsp; &nbsp; scanner := bufio.NewScanner(os.Stdin)&nbsp; &nbsp; fmt.Print("Enter word: ")&nbsp; &nbsp; scanner.Scan()&nbsp; &nbsp; word := scanner.Text()&nbsp; &nbsp; anagrams := factorial(len(word))&nbsp; &nbsp; chars := strings.Split(word, "")&nbsp; &nbsp; word1 := word&nbsp; &nbsp; n := 0&nbsp; &nbsp; for i := 0; i < len(word); i++ {&nbsp; &nbsp; &nbsp; &nbsp; n = strings.Count(word1, chars[i])&nbsp; &nbsp; &nbsp; &nbsp; if n > 0 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; anagrams = anagrams / factorial(n)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; word1 = strings.Replace(word1, chars[i], "", -1)&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; fmt.Println(anagrams)}func factorial(n int) int {&nbsp; &nbsp; factorial := 1&nbsp; &nbsp; for i := n; i > 0; i-- {&nbsp; &nbsp; &nbsp; &nbsp; factorial = i * factorial&nbsp; &nbsp; }&nbsp; &nbsp; return factorial}结果：aab -> 3helo -> 24hello -> 60helllo -> 120

Answer 3

您可以使用一些组合。首先计算每个字符的出现次数。然后使用牛顿符号，您将每个字符放在其位置上。例如给定的单词aabcdee你有7个地方可以放置单个字母，你有重复的 - 双a和双e.所以你使用这个公式，你可以放在7个地方中的2个，然后你可以乘以你可以放置b的地方的数量 - 5个剩余地方中的1个。然后在1/4上。然后在1/3上。然后在2/2上。将这些公式中的每一个相乘都会得到线性时间内的字谜数（如果使用哈希图进行字母计数）。acde