找到5个字母单词，有25个不同的字符
高效地解决字字 (对人类和计算机而言)是目前流行的一切。
一种解决问题的特殊方法让我好奇。这个想法是选择5个有不同字母的单词，这样你就会有25个字符。如果你在游戏中使用这5个单词作为你的前5个猜测，你将有接近100%的机会在你的最后猜测中得到正确的单词(它本质上是所有线索的缩略，你可能会有一些绿色的)。建议使用一组单词(所有这些单词都是有效的英语单词)：
- 砖块
- 格伦特
- 跳起来
- 沃日德
- 蜡质
但这让我想知道:这5个单词组合中有多少是存在的，我开始提出一个递归算法，但我几乎要放弃了。
我最初的想法是：
- 从第一个单词开始
- 减少单词列表中的重叠词
- 选择单词列表中的下一个单词
- 用下一个单词重复一遍
但是，只有当你有一组五个不同的单词的时候，这才能真正发挥作用。
关于这份清单：
- 砖块
- 盛宴
- 格伦特
- 跳起来
- 沃日德
- 蜡质
我将以：[brick, feast, jumpy, vozhd]结束，因为feast先于glent并将其过滤掉，但最终glent将是更好的选择。
我找不到解决这个具体问题的任何算法，所以我想知道是否有任何现有的算法可以应用到这个问题上？
回答 2
Stack Overflow用户
发布于 2022-02-07 08:44:25
这是有可能的暴力-强迫这个。为了提高效率，人们可以用重复字母丢弃所有单词，并对这些单词进行预处理，以使用它们拥有的字母位掩码(有26个字母，因此这符合32位无符号整数)。
然后做一个深度优先搜索，保持一个列表的单词(位掩码)，不相交到目前为止找到的单词。
我写了一些go代码来完成这个任务。它使用了一个简短的单词列表，其中只包含解决方案单词(完整的words列表太长，无法在这里包含)，但是即使在完整的列表中，代码也会在几秒钟内运行。
因为它使用位掩码来表示单词，所以解决方案中可能存在多个字母相同的单词。这个程序显示在中间有|的人。解决方案中只有一对：cylix|xylic：
bling treck waqfs jumpy vozhd
pling treck waqfs jumby vozhd
brick glent waqfs jumpy vozhd
kreng clipt waqfs jumby vozhd
fjord chunk vibex gymps waltz
fjord gucks vibex nymph waltz
prick glent waqfs jumby vozhd
kempt brung waqfs cylix|xylic vozhd
blunk waqfs cimex grypt vozhd
clunk waqfs bemix grypt vozhd它可以在这里运行：https://go.dev/play/p/wVEDjx3G1fE
package main
import (
"fmt"
"math/bits"
"sort"
"strings"
)
var allWords = []string{
"bemix", "bling", "blunk", "brick", "brung", "chunk", "cimex", "clipt", "clunk", "cylix", "fjord", "glent", "grypt", "gucks", "gymps", "jumby", "jumpy", "kempt", "kreng", "nymph", "pling", "prick", "treck", "vibex", "vozhd", "waltz", "waqfs", "xylic",
}
func printSol(res []uint32, masks map[uint32][]string) {
var b strings.Builder
for i, r := range res {
if i > 0 {
b.WriteString(" ")
}
b.WriteString(strings.Join(masks[r], "|"))
}
fmt.Println(b.String())
}
func find5(w []uint32, mask uint32, n int, res []uint32, masks map[uint32][]string) {
if n == 5 {
printSol(res, masks)
return
}
sub := []uint32{}
for _, x := range w {
if x&mask != 0 {
continue
}
sub = append(sub, x)
}
for i, x := range sub {
res[n] = x
find5(sub[i+1:], mask|x, n+1, res, masks)
}
}
func find5clique() {
masks := map[uint32][]string{}
for _, x := range allWords {
m := uint32(0)
for _, c := range x {
m |= 1 << (c - 'a')
}
if bits.OnesCount32(m) == 5 {
masks[m] = append(masks[m], x)
}
}
maskSlice := []uint32{}
for m := range masks {
maskSlice = append(maskSlice, m)
}
sort.Slice(maskSlice, func(i, j int) bool {
return maskSlice[i] < maskSlice[j]
})
find5(maskSlice, uint32(0), 0, make([]uint32, 5, 5), masks)
}
func main() {
find5clique()
}Stack Overflow用户
发布于 2022-08-26 02:07:30
我选择了4个单词:批处理，字段，错误，麝香非常适合所有形式的*命令找不到第五个单词与其余的字母，尽管。
https://stackoverflow.com/questions/71011062
复制相似问题
腾讯云开发者
