找到单词变位词数量的算法?

huangapple go评论89阅读模式
英文:

Algorithm for finding amount of word anagrams?

问题

我知道找到变位词的理论,可以在这里找到。根据我的需求,我需要找到一个单词中可以找到的变位词的数量,不包括重复的变位词

如果允许有重复的变位词,这就相对简单。
aab 有以下变位词:

aab
aab
aba
aba
baa
baa

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

阶乘 := 1

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

// aab -> 6

然而,如果你想要排除重复的变位词,你将把潜在的变位词数量从6减少到3。一个例子是单词 hello,它有120种组合,但只有60种没有重复。

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

hello -> 24 (实际上是60)
helllo -> 24 (实际上是120)

我该如何实现这个目标?

英文:

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?

答案1

得分: 4

如果不考虑单词的有效性,最好放弃使用"anagram"这个词。你只是在询问排列组合。有一个公式可以计算考虑重复的排列组合:

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

对于"helllo":

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

排列组合 = 6! / (1! x 1! x 3! x 1!)
= 720 / 6
= 120
英文:

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

答案2

得分: 0

代码部分已翻译如下:

package main

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

func main() {

	scanner := bufio.NewScanner(os.Stdin)
	fmt.Print("输入单词:")
	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
英文:

Code:

package main

import (
	&quot;bufio&quot;
	&quot;fmt&quot;
	&quot;os&quot;
	&quot;strings&quot;
)

func main() {

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

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

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

	fmt.Println(anagrams)

}

func factorial(n int) int {

	factorial := 1

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

	return factorial

}

Results:

aab -&gt; 3
helo -&gt; 24
hello -&gt; 60
helllo -&gt; 120

答案3

得分: 0

你可以使用一些组合数学的方法。首先,统计每个字符出现的次数。然后使用牛顿符号将每个字符放置在相应的位置上。例如,给定单词

aabcdee

你有7个位置可以放置单个字母,并且有重复的字母 - 双重的a和双重的e。所以你可以使用以下公式:

你可以将a放置在7个位置中的2个位置上,然后将其乘以可以放置b的位置数 - 剩下的5个位置中的1个位置。然后将c放置在4个位置中的1个位置上。然后将d放置在3个位置中的1个位置上。然后将e放置在2个位置中的2个位置上。

将每个公式相乘将给出线性时间内的排列数(如果使用哈希映射进行字母计数的话)。

英文:

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.<br>
so u use that formula<br>
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.<br>
Multiplying each of these formulas will give you number of anagrams in linear time (in case of using hashmap for letter counting).

huangapple
  • 本文由 发表于 2021年8月13日 07:15:27
  • 转载请务必保留本文链接:https://go.coder-hub.com/68765120.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定