所以我知道找到字謎背后的理論，如圖所示。出于我的目的，我需要找到可以從單詞中找到的字謎數(shù)量，排除重復(fù)項(xiàng)。允許重復(fù)，這相當(dāng)簡單。 具有以下字謎：aabaab
aab
aba
aba
baa
baa這個數(shù)量可以通過從字母的數(shù)量計(jì)算階乘來找到factorial := 1for i := len(word); i > 0; i-- {
factorial = i * factorial
}// aab -> 6但是，如果要排除重復(fù)項(xiàng)，則可以將潛在的字謎從6個減少到3個。這方面的一個例子是單詞 ，它有120個組合，但只有60個沒有重復(fù)的組合。hello我編寫了自己的算法，該算法制作了字母地圖并返回了地圖的長度，但這也有問題。hello -> 24 (actually 60)
helllo -> 24 (actually 120)我怎樣才能做到這一點(diǎn)？
3 回答
萬千封印
TA貢獻(xiàn)1891條經(jīng)驗(yàn) 獲得超3個贊
如果這些詞的有效性沒有得到任何考慮，那么最好放棄“字謎”這個詞。你只是在問排列。有一個用于解釋重復(fù)項(xiàng)的排列公式：
對于一個長度的單詞，取排列的基數(shù)，即 。然后，對于單詞中的每個唯一字母，計(jì)算該字母的出現(xiàn)次數(shù)。對于這些字母中的每一個，取出現(xiàn)次數(shù)的階乘，并將排列數(shù)除以它。nn!
對于“地獄”：
n = 6
h = 1, e = 1, l = 3, o = 1
Permutations = 6! / (1! x 1! x 3! x 1!)
= 720 / 6
= 120
慕妹3242003
TA貢獻(xiàn)1824條經(jīng)驗(yàn) 獲得超6個贊
法典：
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
}
結(jié)果：
aab -> 3
helo -> 24
hello -> 60
helllo -> 120
九州編程
TA貢獻(xiàn)1785條經(jīng)驗(yàn) 獲得超4個贊
您可以使用一些組合。首先計(jì)算每個字符的出現(xiàn)次數(shù)。然后使用牛頓符號，您將每個字符放在其位置上。例如給定的單詞
aabcdee你有7個地方可以放置單個字母，你有重復(fù)的 - 雙a和雙e.
所以你使用這個公式
，你可以放在7個地方中的2個，然后你可以乘以你可以放置b的地方的數(shù)量 - 5個剩余地方中的1個。然后在1/4上。然后在1/3上。然后在2/2上。
將這些公式中的每一個相乘都會得到線性時間內(nèi)的字謎數(shù)（如果使用哈希圖進(jìn)行字母計(jì)數(shù)）。acde
- 3 回答
- 0 關(guān)注
- 101 瀏覽
添加回答
舉報
0/150
提交
取消