Python是否有可生成带重复的可变长度排列的库函数适配Spelling Bee场景？

核心思路说明 #

你之前了解的permutations、combinations不满足需求是因为这两个方法默认不允许元素重复出现，自然没法生成包含重复字母的单词（比如diced里的两个d、riffraff里的多个f），itertools.product本身就支持重复元素生成，完全可以匹配你的需求。但更推荐优先用词库反向过滤的方案，效率远高于正向生成所有候选。

方案1：词库反向过滤（生产环境首选） #

正向生成长度4~12的所有候选字符串总规模达到7^4 + 7^5 + ... +7^12 ≈ 13.8亿，完全没有必要，直接用现有英文词库做规则过滤即可，秒出结果。

过滤规则 #

只需要同时满足3个条件：

• 单词长度在你设置的[min, max]区间内
• 单词包含必填字母
• 单词的所有字符都属于给定的7个字母集合

示例代码 #

def spelling_bee_generator(letters: str, required_char: str, min_len: int=4, max_len: int=12) -> list[str]:
    allowed_chars = set(letters.lower())
    required_char = required_char.lower()
    valid_words = []
    # 可替换为你自己的英文词库路径，Linux系统默认自带词库路径为/usr/share/dict/words
    with open("/usr/share/dict/words", "r", encoding="utf-8") as f:
        for line in f:
            word = line.strip().lower()
            if len(word) < min_len or len(word) > max_len:
                continue
            if required_char not in word:
                continue
            if all(c in allowed_chars for c in word):
                valid_words.append(word)
    return valid_words

调用示例 #

对应2021年10月12日的题目，调用方式如下：

result = spelling_bee_generator("cpithde", required_char="c", min_len=4, max_len=12)

返回结果会直接包含pitch、pitched、diced等所有合规单词，不需要额外做字典校验。如果需要筛选使用了全部7个字母的高分单词，额外加一句set(word) == allowed_chars的判断即可。

方案2：itertools正向生成候选（仅适合小范围测试） #

如果必须要先生成所有符合拼写规则的候选再做字典校验，可以用itertools.product实现，它支持指定长度生成允许重复元素的所有字符序列，刚好匹配你的需求。

示例代码 #

import itertools

def spelling_bee_generator(letters: str, required_char: str, min_len: int=4, max_len: int=12) -> set[str]:
    allowed_chars = list(letters.lower())
    required_char = required_char.lower()
    candidates = set()
    # 遍历要求的所有长度生成候选
    for length in range(min_len, max_len + 1):
        for char_seq in itertools.product(allowed_chars, repeat=length):
            word = "".join(char_seq)
            if required_char in word:
                candidates.add(word)
    return candidates

这个方案的缺点是生成的候选规模极大，仅适合max_len <= 8的场景使用，超过这个长度运行效率会非常低。

内容的提问来源于stack exchange，提问作者Bill Torcaso