从字母生成最佳单词组合以最大化拼字游戏分数（基于单词长度）

Question

我的目标：

• 给定 36 个字母的字符串，找到使 Scrabble 总分最大化的单词组合

评分规则：

• 对于 4-9 个字母之间的单词，每个单词的字母数为 3 乘以 5
• 单词 >= 10 个字母，平分 30 分

抱歉，我是 Python 或其他编码语言的新手。我不知道如何列出所有可能的单词组合而不生成 36！排列 - 如果我这样做（当然很愚蠢），我可以简单地继续将字符串从第一个字母分割到最后一个字母，以形成所有可能的单词（在下一节中显示）

我目前的想法（看起来效率极低）：

重点关注 4-10 个字母单词的有限搜索空间，并使用字典来修剪无效组合。

1. 生成长度为 4-10 个字母的所有可能的字母组合
2. 过滤组合到有效的字典单词
3. 计算每个有效单词的分数
4. 找到使总分最大化的有效单词组合
   • 使用 4 个长度为 9 的单词，最高得分为 120 分

实施：

• 36 个字母的字符串
• 生成字母组合的迭代器
• 检查单词有效性的词典
• 存储单词组合的元组或列表
• 计算单词组合得分的函数
• 回溯搜索寻找最优组合

但我问这个问题是因为我真的想避免这种低效的方法：想象一下我创建了一个 36！排列，对于每个排列，我在循环中拆分字符串以生成所有可能的单词组合（元组），然后比较所有元组的分数，以确定玩家在任何给定的 36 个字母中可以生成的最高可能分数。对我来说，使用残酷的计算力来解决一个简单的（在某种程度上）游戏似乎很荒谬。

尝试避免您的建议：

• 生成全部 36 个！排列 - 不可行
• 对所有组合进行排序 - 效率低下

Answer 1

不用考虑 36 个字母的每一种排列，另一种方法是 解决这个问题的方法是生成有效词，然后枚举所有 有效单词的组合。什么是有效词？我来解释一下。

给定一本字典和一个包含 36 个字母的列表，有效单词是所有单词 字典中可以用这36个字母来构造。找到后 有效的单词，可以使用回溯算法来枚举所有可能的单词 可以组合在一起的有效单词的组合（重复） 使用 36 个字母。

该算法的时间复杂度是有效单词集大小的多项式。 由于最多可以使用 9 个四字母单词来匹配这 36 个字母， 这意味着该算法的运行时间为 O(n^9)，其中 n 是 有效单词的集合。

这里是Python中的实现（注意我使用的是Linux字典文件，所以你 如果您在不同的平台上，可以更改字典文件）。算法完成后，最后打印的一组文字将是最优解之一。如果您只想检查是否有 120 分的解决方案，那么应该运行得很快，因为有效单词数会很低，并且只需要检查最多四个单词的组合。您可以使用

MAX_WORD_SIZE

和

MIN_WORD_SIZE

变量来查看哪种效果最好。您还可以将

LETTERS

设置为您想要的任何值。我只是用 ASCII 字符随机初始化它。

import random
import string
from typing import List, Dict
from collections import Counter

DICT_FILE = "/usr/share/dict/words"
MIN_WORD_SIZE = 4
MAX_WORD_SIZE = 10
LETTERS = "".join(random.choice(string.ascii_lowercase) for _ in range(36))

def is_valid(word: str, letter_counts: Dict[str, int]):
    for c in word:
        if letter_counts[c] == 0:
            return False
        letter_counts[c] -= 1
    return True


def valid_words(letters: str) -> List[str]:
    valid = []
    letter_counts = Counter(letters)
    with open(DICT_FILE) as f:
        for line in f:
            word = line.strip()
            if (
                "'" in word or 
                len(word) < MIN_WORD_SIZE or
                len(word) > MAX_WORD_SIZE
            ):
                continue
            if is_valid(word, letter_counts.copy()):
                valid.append(word)
    return valid


def remove_letters(word: str, counts: Dict[str, int]):
    for c in word:
        counts[c] -= 1

def add_letters(word: str, counts: Dict[str, int]):
    for c in word:
        counts[c] += 1

def find_optimal(valid_words: List[str], letters: str):
    curr_words = []
    counts = Counter(letters)
    n = len(valid_words)

    def find_words(i: int, num_letters: int):
        if i == n or num_letters < 4:
            return
        for j, word in enumerate(valid_words[i:], i):
            if is_valid(word, counts.copy()):
                remove_letters(word, counts)
                curr_words.append(word)
                yield from find_words(j, num_letters - len(word))
                yield curr_words.copy()
                curr_words.pop()
                add_letters(word, counts)

    yield from find_words(0, len(letters))


def score(word_combos: List[str]):
    return sum(
        min(
            (len(word) - 3) * 5, 
            30,
        ) for word in word_combos
    )


if __name__ == "__main__":
    valid = valid_words(LETTERS)
    latest_highest_score = 0
    latest_best_words = []
    for word_combos in find_optimal(valid, LETTERS):
        curr_score = score(word_combos)
        if curr_score >= latest_highest_score:
            latest_highest_score = curr_score
            latest_best_words = word_combos
            print(word_combos, latest_highest_score)