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

Question

所以我知道找到字谜背后的理论，如图所示。出于我的目的，我需要找到可以从单词中找到的字谜数量，排除重复项。允许重复，这相当简单。 具有以下字谜：aabaab 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 = 6

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

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

= 720 / 6

= 120

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

Answer 3

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

aabcdee你有7个地方可以放置单个字母，你有重复的 - 双a和双e.
所以你使用这个公式
，你可以放在7个地方中的2个，然后你可以乘以你可以放置b的地方的数量 - 5个剩余地方中的1个。然后在1/4上。然后在1/3上。然后在2/2上。
将这些公式中的每一个相乘都会得到线性时间内的字谜数（如果使用哈希图进行字母计数）。acde