优化itertools组合速度：荷兰语单词轮盘谜题求解方案

DevOps 小满

2026-8-10

问题背景

我正在给女友制作一款荷兰语单词轮盘谜题：谜题包含4个轮盘，每个轮盘对应一个7字母单词的唯一变位词；当正确旋转所有轮盘后，会形成7个有效的4字母单词。

我当前的实现思路是：用Python的itertools结合4字母词表与7字母词表，先将所有7字母单词按字母排序后存入集合seven_set，再遍历所有7个4字母单词的组合，检查每个位置（共4个位置）的7个字母排序后是否存在于seven_set中。

但遇到了两个核心问题：

4字母词表有1052个单词，组合数高达277万亿级，计算量完全无法承受；
强行缩小词表到30个单词时，仅能找到1-3个符合要求的7字母单词，无法满足谜题需求。

举个有效组合的例子：auto、duif、eend、ogen、papa、tram、vita这7个4字母词，它们的第1位字母排序后对应7字母词voetpad，第3位字母排序后对应7字母词patient。

当前使用的核心代码如下：

import itertools

four_letter_words = [...]  # 加载4字母词表
seven_set = {''.join(sorted(word)) for word in [...]}  # 加载7字母词表并生成排序集合

for a in itertools.combinations(four_letter_words, 7):
    correct = True
    for x in range(0, 4):
        check_string = a[0][x] + a[1][x] + a[2][x] + a[3][x] + a[4][x] + a[5][x] + a[6][x]
        check_sorted = ''.join(sorted(check_string))
        if check_sorted not in seven_set:
            correct = False
            break
    if correct:
        f = open("options.txt", "a")
        f.write(' '.join(a) + "\n")
        f.close()

我现在需要解决两个问题：

能否加速这段代码？
是否存在无需高迭代量的组合查找方法？能否在不遗漏可能组合的前提下，智能缩小4字母词表范围？（已移除荷兰语中含q、x、y的罕见单词）

解决方案

一、加速现有代码的方法

1. 优化IO操作

当前每次找到有效组合都打开/关闭文件，IO开销极大。改为提前打开文件，找到结果直接写入，最后统一关闭：

with open("options.txt", "a") as f:
    for a in itertools.combinations(four_letter_words, 7):
        correct = True
        for x in range(4):
            check_string = ''.join(word[x] for word in a)
            check_sorted = ''.join(sorted(check_string))
            if check_sorted not in seven_set:
                correct = False
                break
        if correct:
            f.write(' '.join(a) + "\n")

2. 预计算词的位置字母

将每个4字母词转换为元组（比字符串索引更快），避免循环中重复的字符拼接与索引操作：

# 预处理4字母词表
processed_four = [tuple(word) for word in four_letter_words]

# 循环中修改为：
check_string = ''.join(word[x] for word in a)

3. 并行计算

利用multiprocessing.Pool将组合遍历任务拆分到多个CPU核心并行处理，大幅提升CPU密集型任务的效率：

import multiprocessing

def check_combination(comb):
    for x in range(4):
        check_sorted = ''.join(sorted(word[x] for word in comb))
        if check_sorted not in seven_set:
            return None
    return ' '.join(comb)

if __name__ == "__main__":
    processed_four = [tuple(word) for word in four_letter_words]
    seven_set = {''.join(sorted(word)) for word in [...]}  # 加载7字母词表集合
    with multiprocessing.Pool() as pool:
        results = pool.imap_unordered(check_combination, itertools.combinations(processed_four, 7))
        with open("options.txt", "a") as f:
            for res in results:
                if res:
                    f.write(res + "\n")

4. 提前剪枝

在遍历组合时，不用等凑齐7个词再检查，每加入一个新词就验证当前已选词的各位置字母是否有可能和剩余词组成有效7字母词：
比如选前2个词后，对每个位置x，当前2个字母的组合必须能和另外5个字母组成seven_set中的某个字符串。可以预计算每个位置x的字母组合到可能的7字母字符串的映射，快速判断可行性。

二、减少迭代量的核心思路：反向查找

当前从4字母词组合入手的思路计算量爆炸，反向从7字母词组合入手能大幅降低复杂度：

1. 思路转换

谜题的本质是：找到4个7字母词（每个对应一个轮盘），将每个词排列成字符串后，每一列（共7列）的4个字母组成一个有效的4字母词。

相比C(1052,7)的天文数字，若7字母词表有M个单词，C(M,4)的组合数会小几个数量级（比如M=1000时，C(1000,4)仅约41亿，远小于277万亿）。

2. 具体实现步骤

预构建4字母词的查找集合：four_set = set(four_letter_words)，方便O(1)查询。
遍历所有4个7字母词的组合：for combo in itertools.combinations(seven_letter_words, 4)。
对每个组合中的4个词，生成所有可能的排列（或仅循环移位，若轮盘只能旋转而非任意排列），检查每一列是否为有效4字母词。
若找到符合条件的排列，即可反向生成对应的7个4字母词组合。

3. 智能缩小4字母词表范围

在反向查找前，可先对4字母词表做以下过滤：

字母合法性过滤：统计所有7字母词中出现的字母集合valid_chars，移除所有包含valid_chars外字母的4字母词。
位置字母匹配过滤：对每个位置（0-3），收集所有7字母词中该位置可能出现的字母（准确说，是所有7字母词排序后包含的字母），移除那些在某个位置的字母无法参与组成任何7字母词变位词的4字母词。
词的字母交集过滤：对于一个4字母词，它的4个字母必须分别能出现在某个7字母词的字母集合中（即每个位置的字母都属于至少一个7字母词的字母集合），否则该词不可能出现在任何有效组合中。

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

优化itertools组合速度：荷兰语单词轮盘谜题求解方案

一、加速现有代码的方法 #

1. 优化IO操作 #

2. 预计算词的位置字母 #

3. 并行计算 #

4. 提前剪枝 #

二、减少迭代量的核心思路：反向查找 #

1. 思路转换 #

2. 具体实现步骤 #

3. 智能缩小4字母词表范围 #