英文:
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 (
"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
答案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).
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论