65.9K
CodeProject 正在变化。 阅读更多。
Home

字谜 - 文字游戏： 第二部分

charles922
starIconstarIconstarIconstarIconstarIcon

5.00/5 (3投票s)

2018 年 6 月 28 日

CPOL

7分钟阅读

viewsIcon

12814

downloadIcon

178

字谜生成器

引言

在我上一篇文章《词语的乐趣第 1 部分》中，我向您展示了一个生成回文（正反读都相同的短语）的算法。我曾尝试开发一个生成“字谜”（通过重排另一个单词或短语的字母而形成的单词或短语，例如，“Old West Action”是“Clint Eastwood”的字谜）的算法。然而，我的尝试导致了一个运行缓慢且无法为给定输入生成所有可能字谜的程序。因此，我找到了 Parth Parekh 的一个非常有趣的算法，并在第 2 部分中，我将 Parth 的 Java 代码转换成了 C#。我将解释 Parth 的优秀算法，并指出 Java 和 C# 之间的一些差异。

Using the Code

下载并解压项目，然后用 Visual Studio 打开 AnagramGenerator.sln。它包含三个项目：

  1. AnagramGenerator - 主程序，一个用于通过命令行生成字谜的控制台项目
  2. AnagramUnitTestProject - 一个单元测试项目
  3. WebServiceLib - 一个Web 服务库，用于调用在线语法检查 API 来验证短语或句子的有效性

按F6键构建解决方案。

数据结构

我想讨论的第一个数据结构是 HashSet<String>。HashSet 是一个不包含重复元素且元素顺序不确定的集合。在此示例中，该集合仅包含 string。那么，HashSet<HashSet<String>> 会是什么呢？它是一个包含集合的集合——这些集合包含 string。Java 中的等效类型也称为 HashSet，它有一个用于合并两个集合（.NET 中没有此方法）的 addAll() 方法。第二个数据结构是 .NET 类 SortedDictionary，它是一个按键排序的键/值对集合。我在代码中使用它，而 Parth 使用的是 Java 的 TreeMap。

单词列表文件

在他的 gitub 项目中，Parth 提供了一个名为 wordlist.txt 的文件，其中包含超过 100,000 个单词。依我拙见，这会导致给定单词产生过多的字谜，因此我提供了一个名为 3000CommonWords.txt 的文件，其中包含 3000 个常用英语单词，这样生成的字谜数量会减少，但更易读。我还提供了一个名为 testingWords.txt 的文件用于测试。

我添加的一项增强功能是能够使用在线语法检查器来确定生成字谜的语法正确性。此功能对应的代码位于一个名为 WebServiceLib 的库中，该库下面将进行描述。

命令行参数

程序提供三个命令行参数：

  1. 单词列表文件的名称，一个每行一个单词的文本文件
  2. 要从单词列表文件中使用的单词的最小长度
  3. 要生成字谜的单词或短语。Parth 的代码会附加参数 3 及之后的参数来创建此短语；为简单起见，此版本仅假设第三个参数用引号括起来，如上面图片中的示例所示。

代码详情

SortedWordDictionary 类包含一个名为 loadDictionaryWithSubsets() 的方法。它读取单词列表文件并构建一个名为 SortedDictionary<String, HashSet<String>>sortedStringMap 的数据结构。如前所述，在 Java 代码中，使用 TreeMap 而不是 .NET 的 SortedDictionary。首先，我们来看测试文件 testingWords.txt。它包含单词 old、west、action、stew、meat、team、mate、cation、wets。（如果您想知道，cation 是带正电的离子。）使用“Clint Eastwood”作为我们要生成字谜的短语，通过名为 Canonical() 的方法去除空格和标点符号，并将其存储在名为 charInventory 的字符数组中。loadDictionaryWithSubsets 首先会忽略任何不是子集（通过 isSubset() 方法确定）的单词。因此，meat、team、mate 会被忽略，因为它们不是我们 charInventory 的子集。对于剩余的单词，sortedStringMap 中的键是根据 sortWord() 方法按字母顺序排序的单词。值是一个包含该单词所有字谜的 HashMap，因此处理完文件后，sortedStringMap 如下所示：

键 值
acinot action, cation
dlo old
estw west, stew, wets

getDictionaryKeyList 获取键的 List<String>，即 acinot、dlo、estw。（Java 有一个名为 keySet() 的方法可以做到这一点，所以我们称之为“键集”。）接下来，在 FindAllAnagrams() 中，我们遍历这些键，调用 findAnagrams() 方法。findAnagrams() 使用 isEquivalent() 方法递归地在 charInventory 数组中查找字谜。findAnagrams() 使用 isSubset() 方法查找整个 charInventory 单词的字谜。它还使用 isSubset() 方法查找包含多个单词的字谜。因此，从“clinteastwood”中的字符的 charInventory 开始，我们取第一个键 acinot，注意到它是一个子集，并从 charInventory 中删除所有这些字符，剩下“lestwod”。我们继续递归，使用下一个键 dlo，并从 charInventory 中删除这些字符，只剩下“estw”。最后，从 charInventory 中删除最后一个键 estw 中的字符，findAnagrams() 返回。请注意，对于最后一个键 estw，isEquivalent 为 true。当 findAnagrams() 返回给调用者时，dictWordAnagramsSet 包含三个键。mergeAnagramKeyWords() 方法将实际单词列表文件中的单词合并起来——例如，对于键“acinot”的实际单词文件“action”——对于键集中的所有单词。因此，在调用 setMultiplication() 之前，mergeAnagramKeyWords() 中的 anagramsSet 包含 3 个仅包含实际单词的集合

  1. west, stew, wets
  2. old
  3. action, cation

setMultiplication() 方法返回笛卡尔积（使用LINQ 可以简化笛卡尔积的生成）。最后，当 FindAllAnagrams() 返回时，我们得到了 6 个字谜。

 action old west
 cation old west
 action old stew
 cation old stew
 action old wets
 cation old wets

它们与 Parth 的结果有些不同，其原因是：在 Java 的 mergeWordToSets() 方法中，mergedSets 的顺序是 dlo estw，而在 C# 版本中，顺序相反，是 estw dlo。这是因为 HashSet 的 Add 方法假定没有特定顺序。我在 mergeAnagramKeyWords() 中添加了一个对随机生成器的调用，该随机生成器是一个名为 Shuffle() 的扩展方法，因此后续调用 AnagramGenerator 会产生略有不同的结果。

Web 服务库

WebServiceLib 类有一个方法 public String CheckGrammar(String sentence)，它从在线语法检查器返回一个 string，用于给定句子。市面上有许多在线语法检查器，我选择了一个虽然免费但需要注册才能获得密钥的。请参阅 WebService.cs 中我使用的服务的首页 URL。如果您有密钥，请将 WebService.cs 中显示 String appKey = "Your Key Here"; 的行替换为您的密钥。例如，Web 服务 API 对“Old west action.”的返回值是：

{ "status":"1","message":"Successfully checked","error_grammar_count_total":0,
  "error_grammar_percent":"0%",
"check_grammar_feedback":[]}

0% 错误，表明语法正确。语法错误的句子百分比会更高。在 Main 程序中，我演示了如何调用 Web 服务并从 Web 服务 API 返回值中提取百分比，并将其与生成的字谜一起显示（在 Main 程序中将 grammarCheck 设置为 true 以启用语法检查）。包含调用语法检查 API 结果的程序输出如图上面图片所示。

结果

以下是使用“Clint Eastwood”和两个单词列表文件进行测试的结果：

单词列表文件 找到的字谜数量
3000CommonWords.txt 227
wordList.txt 59647

结论

Parth 的算法快速而优雅，从 Java 转换为 C# 也很直接。我发现 C# 缺乏 Java 的 addAll() 方法很恼人，但 .NET 的 SortedDictionary、ToList() 和 ToCharArray() 弥补了这一点。

Visual Studio (VS) 和 Eclipse 是当今最流行的两个 IDE。Eclipse 具有一些有趣的功能。例如，要模拟 VS 的“转到定义”（F12）命令，在 Eclipse 中，您只需按住 Ctrl 键并将鼠标指针悬停在要定义的项上。

历史

  • 版本 1.0.0.0
© . All rights reserved.