Find 5 letter words with 25 distinct characters

Question

高效地解决单词（对于人类和计算机）现在非常流行。

解决单词的一种特殊方法让我很好奇。这个想法是选择 5 个具有不同字母的单词，这样您最终将得到 25 个字符。如果您使用这 5 个单词作为游戏中的前 5 个猜测，您将有接近 100% 的机会在最后一次猜测中得到正确的单词（它本质上是所有线索的字谜，您可能会得到一个一些绿色的）。建议使用一组单词（所有单词都是有效的英语单词）：

• 砖
• 格兰特
• 神经兮兮的
• 沃日德
• 宗教与宗教基金

但这让我想知道：这 5 个单词组合中有多少个，我开始制定递归算法，但我几乎要放弃了。

我最初的想法是：

• 从第一个单词开始
• 减少单词列表中的重叠单词
• 选择单词列表中的下一个剩余单词
• 重复下一个单词

但这只有在您有一组按顺序排列的五个不同单词时才真正有效。

对于此列表：

• 砖
• 盛宴
• 格兰特
• 神经兮兮的
• 沃日德
• 宗教与宗教基金

我最终会得到：[brick, feast, jumpy, vozhd]因为feast出现在前面glent并将其过滤掉，但最终glent会是更好的选择。

我无法找到针对这个特定问题的任何算法，所以我想知道是否有任何现有算法可以应用于此？

Answer 1

可以通过暴力破解来实现这一点。为了提高效率，可以丢弃所有具有重复字母的单词，并对这些单词进行预处理以使用它们具有的字母的位掩码（有 26 个字母，因此适合 32 位无符号整数）。

然后进行深度优先搜索，维护与目前找到的单词不相交的单词列表（位掩码）。

我写了一些执行此操作的 go 代码。它使用仅包含解决方案单词的缩短的单词列表（完整的单词列表太长，无法包含在此处），但即使使用完整的列表，代码也会在几秒钟内运行。

由于它使用位掩码来表示单词，因此解决方案中可能存在多个具有相同字母的单词。该节目展示了那些介于|两者之间的人。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()
}