我收到一位读者的一封很棒的信，其中有一个谜题需要解决，所以让我们深入研究一下，好吗？ 这是他写的内容

我一直是《Linux Journal》专栏的忠实读者。多年来，我阅读它并学到了很多关于 shell 脚本的知识，但还不足以独自解决一个难题。

我的父母在他们客房的架子上放了一套大约 12 个木块，每个木块的面上都印有字母或符号。多年来，我每次拜访都会排列这些木块来拼写新的信息，我开始考虑我应该能够编写一个脚本，给我提供可以用这套木块同时拼写的所有可能的单词。

我首先为每个木块制作一个数组，其中每个位置都保存一个字母。我的想法是遍历这 12 个木块的集合，对于每个木块，以与我循环遍历行/列网格大致相同的方式打印六个字母（或非字母的空间），然后将结果与字典进行比较以查找有效单词。但我的解决方案只能处理一种木块组合。我如何考虑所有可能的木块组合呢？

这是一个有趣的难题，部分原因是涉及的组合数量。如果我们从数学开始，每个木块将有六个面，这意味着您可以创建 6¹² 种可能的字母组合——总共 2,176,782,336 种不同的可能性。

现在，让我们假设您说“哎呀！”并决定将自己限制为仅六个字母的单词。这同样疯狂，因为第一个木块可以是 12 个中的任何一个，然后第二个木块是剩余 11 个中的一个，依此类推。因此，12*11*10*9*8*7 给出了我们木块组合的数量（总计 665,280 种可能性）。但每个木块可以显示六个面中的任何一个，因此它要多出许多倍——实际上，根本没有减少多少。

如果我们每秒可以检查 1,000 个单词，那么仍然需要数年时间才能遍历每种组合。因此，我们需要做一些比在字典中进行暴力查找更聪明的事情。

我们真正可以减少可能性数量的地方是决定每个木块都具有相同的字母集，因此对于单词中的每个位置，只有六个可能的选项。这意味着对于一个六个字母的单词，我们有 6*6*6*6*6*6 种可能性，即 46,656 种。

这样就好多了！ 让我们假设每个木块都是相同的，并且具有字母 e、t、a、o、l 和 n，根据维基百科，这些字母恰好是英语中最常见的六个字母，按顺序排列。

注意：使所有木块都具有相同的字母会大大降低我们搜索的复杂性，因为现在顺序无关紧要，但真正的木制字母块是不同的，因此，尽管这对于本专栏来说可能是一个很好的假设，但它不太可能与您父母家中的实际木块相匹配。

为了检查可以从这些木块构建的四个字母的单词，我们现在可以对完全枚举的英语词典进行正则表达式搜索

$ grep -E '^[etaoln][etaoln][etaoln][etaoln]$' dictionary

为了测试目的，我将使用的词典是 SourceForge.net 上提供的“linuxwords”词典：http://sourceforge.net/projects/souptonuts/files/souptonuts/dictionary。

结果是

alee
aloe
anal
anon
ante
lane
late
lean
lent
loan
lone
loon
loot
neat
neon
none
noon
note
onto
tale
tall
teen
tell
tent
toll
tone
tool

这很容易。

更好的是，我们可以减少正则表达式表示法，并通过使用这个正则表达式使其更容易检查更长的单词

^[etaoln]{4}$

{4} 表示法指示该集合必须连续匹配四次才有效，^ 匹配行首，$ 匹配行尾。

如果我们想检查六个字母的单词，这很容易

$ grep -E '^[etaoln]{6}$' dictionary
allele
atonal
latent
nettle
talent
tattoo
tenant
$

让我们全力以赴，尝试更长的单词

$ grep -E '^[etaoln]{7}$' dictionary
antenna
$ grep -E '^[etaoln]{8}$' dictionary
annotate
antennae
neonatal

我们没有找到任何 9-12 个字母的匹配项，因此我们可能无法在单个、拼字游戏杀手级单词中使用所有木块。

下一个合乎逻辑的步骤是拥有所有木块上所有字母的地图，但随后我们可以看到，如果“A”是第一个木块上所有字母的集合，“B”是第二个木块上的，“C”是第三个木块上的，依此类推，这意味着我们需要针对以下内容测试五个字母的单词：ABCDE、ABCD、ABCDG、ABCDH、ABCDI、...、ABCDL、ABCEDF 等等。

请记住，“A”可能是 [abcde]，“B”可能是 [cdefgh]，依此类推，具体取决于木块的实际标签方式。简而言之，这有很多疯狂的可能性，因此我们又回到了暴力破解根本行不通的情况。

从不同的角度来看这个问题，如果每个木块的每个面上只有一个字母怎么办？ 现在我们谈论的是拼字游戏图块，您的牌架可能是七个字母 AEFRGHM。 您可以从这些字母中造出多少个单词？

事实证明，这是一个容易得多的问题。找出答案的一种方法是简单地生成这些字母的所有可能组合，并针对字典对其进行测试（暴力破解解决方案），这将是 7*6*5*4*3*2*1 (7!) 种可能性，或大约 5000 种七个字母的组合。

为此，我们可以使用相同的正则表达式对字典进行第一次过滤

grep -E '^[aefrghm]{7}$' dictionary

这表明实际上有两个单词符合这些标准：grammar 和 referee。但是，那不对！为什么？

因为正则表达式没有考虑到一旦使用了一个字母，就不能再次使用它。用一个 e 无法拼写“referee”，无论我们多么希望如此。

那么现在怎么办？ 好吧，我说过正则表达式只是一个起点，对吧？ 因此，第二步是根据实际的可用字母池检查已识别的可能性。

为此，让我们做一些可能不直观的事情。 让我们对每个单词中的字母进行排序，使其按字母顺序排列，然后也对可用字母池中的字母进行排序。 例如，“grammar”变为“aagmmrr”。

如何做到？ 事实证明代码很容易

$ echo grammar | grep -o . | sort |tr -d "\n"

但是，我的空间用完了，所以请继续关注。 我们下次再回到这个话题。

特别感谢我的朋友 Jesse Stay 在正则表达式和最后一个字母排序技巧方面的帮助。