回文 - 文字的乐趣：第 1 部分

引言

为了继续学习 Python，我想了一个很有成效的练习，就是将一个 Python 程序转换为 C#。Peter Norvig 的 Python 回文生成器 提供了一个理想的起点。为了让读者能够轻松地在 C# 代码和 Norvig 先生的 Python 代码之间切换，我保留了他 Python 代码中方法的拼写。因此，像 FxCop 这样的分析工具会警告诸如 read_dict 这样的方法名，而在 C# 中通常应该是 ReadDictionary。

我一直着迷于回文——那些正反读都一样的短语——这可以追溯到我年轻的时候，有人给我展示了著名的“Madam, I'm Adam”和“A man, a plan, a canal, Panama!”这两个回文。手工制作回文非常费力，所以当我发现可以让电脑来完成这项工作时，我非常感兴趣。我第一次看到计算机生成的回文是在 Peter van der Linden 1994 年的《Expert C Programming》的第 4 章中，他展示了一个近 300 字的回文。van der Linden 先生的书没有提供生成回文的代码，而是将其作为一个练习。所以，我早期用 C 编写回文生成器的尝试既笨拙又效率低下。幸运的是，Norvig 先生的算法优雅且易于在 C# 中实现。让我们看看它是如何工作的。

词典

在深入研究算法细节之前，我想描述一下 read_dict() 方法。它读取包含每行一个单词或短语的字典文件，并将它们放入两个 List<String> 中。一个列表（_fw）包含按原顺序的单词，第二个列表（_bw）包含反向排序的单词，因此“cat”被存储为“tac”。reverse() 方法用于反转 String。我对 Norvig 先生的 read_dict() 方法做了一个小修改，允许您从给定的起始和结束行号读取。顺便说一句，这演示了 C# 中一个经常被忽视的功能，称为可选参数。我提供了一个比 Norvig 先生提供的 npDict.txt 字典小得多的版本，名为 npdictPeterVanDerLinden.txt。npdictPeterVanDerLinden.txt 中的单词来自 van der Linden 先生的书，并且经过优化，可以快速生成多个回文。（诚然，这些回文通常没有意义，但这个程序的重点是算法。）

在 App.config 中设置您想使用的字典文件的名称，例如

<setting name="Dictionary" serializeAs="String">
	<value>C:\MyDocuments\Palindrome\Dictionary\npdict.txt<value>
</setting>

算法

PalPython 类有两个 String 列表，一个用于构建回文的左侧，另一个用于构建回文的右侧。

public List<String> left { get; set; }
public List<String> right { get; set; }

在 init() 方法中，我们首先创建“种子”单词，即“A man, a plan, a canal, Panama”。（在程序运行时，我们将忽略标点符号和空格。请参阅 canonical() 方法了解如何实现这一点。我们实际上还将右侧存储为反向，并且单词中的字母也反向。）我们将“amanaplan”放入 left，将“acanalpanama”放入 right。

接下来，我们找到与另一侧文本不匹配的子字符串。在下表中，该子字符串（本身就是一个回文），aca，位于右侧，并在下表中以粗体显示。

左侧	右侧
amanaplan	acanalpanama

接下来，我们在字典中搜索以子字符串 aca 开头的单词，并使用 extend() 方法将其添加到左侧。假设我们选择了短语 a catnip，正如前面提到的，它存储为 acatnip，不带空格。我们将其添加到左侧，然后再次找到与另一侧文本不匹配的子字符串。在下表中，该子字符串 tnip 位于左侧，并在下表中以粗体显示。

左侧	右侧
amanaplanacatnip	acanalpanama

由于 tnip 不是回文，我们需要在字典中找到以 pint（tnip 的反向）结尾的单词。假设我们从字典中获取了 apint。使用 extend() 方法将其添加到右侧，注意子字符串，即单个字母 a，是一个回文， voilà，我们得到了一个回文（尽管有点傻）：A man, a plan, a catnip, a pint, a canal, Panama!

左侧	右侧
amanaplanacatnip	apintacanalpanama

但如果我们获取第二个单词后没有得到回文怎么办？这时 Norvig 先生出色的 backtrack() 方法就派上用场了。假设我们的字典中有 acatalpa、acaret 和 abater（A Catalpa 是一种树；A Caret 是您键盘上数字 6 上方的符号；A Bater 是鞣革工人。）现在当我们尝试匹配子字符串 aca 时，匹配 aca 的两个单词是 acatalpa 和 acaret，并将它们放入堆栈（如下所述）。在下表中，我们将 acatalpa 添加到左侧（有关详细信息，请参阅 extend() 方法）。

左侧	右侧
amanaplanacatalpa	acanalpanama

但是，字典中没有以 aplat（子字符串 talpa 的反向）结尾的单词。所以我们 回溯，从 left 中移除 acatalpa，然后尝试下一个，即 acaret，通过在 search() 中将其从堆栈中弹出，并使用 extend() 添加到左侧。

左侧	右侧
amanaplanacaret	acanalpanama

现在我们查找字典中以 ter（子字符串 ret 的反向）结尾的单词。我们获取 abater 并将其添加到右侧。

左侧	右侧
amanaplanacaret	abateracanalpanama

子字符串现在是 aba（本身就是一个回文），惊喜的是，我们又找到了一个回文：A man, a plan, a caret, a bater, a canal, Panama! 找到回文后，它们会被写入一个名为 pallog<process id>.txt 的文件，例如 pallog8080.txt。

Using the Code

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

1. Palindrome - 主项目
2. UnitTestProjectPal - 单元测试项目

按 F6 键生成解决方案。请记住按照 上面 的说明设置您想使用的字典文件的名称。

代码详情

PalPython 类是主类，它有许多属性，包括两个 Dictionary 项。public Dictionary<String, String>_truename，它保存规范化单词的真实名称；public Dictionary<String, int>seen，它跟踪一个单词是否已被用于构建当前回文。

PalPython 中使用的关键类是 MyStackItem。它由当前子字符串和与之匹配的单词组成，这些单词存储在 Stack 中。一个 MyStackItem 的堆栈保存在它们自己的堆栈中，即 public Stack<MyStackItem>wordStack。在程序运行时，子字符串和匹配它的单词会被放入一个 MyStackItem 对象中，然后该对象被压入 wordStack。该类本身非常简单，只有两个属性；事实上，用于调试的 PrintStack(), PrintWords(), and ToString() 方法实际上是该类中最复杂的部分！稍后我们将查看 PrintStack() 和 PrintWords()。

public class MyStackItem
{
	public String Substring { get; set; }
	public Stack<String> Words { get; set; }
	...
}

在使用 Python 的调试器时（我使用的是 IDLE Version 2.7），我在 search() 方法中调用 self.extend() 之后添加了以下代码，以打印与子字符串匹配的当前单词列表以及当前堆栈。

	print (words)
	print (self.stack)

例如，对于子字符串 aca（使用 npdictPeterVanDerLinden.txt 字典文件），在 IDLE 的 Python shell 中输出如下：

	['acalamus', 'acanal', 'acaret', 'acat', 'acat', 'acatalpa', 'acatnip', 'acaw']
	[('aca', ['acalamus', 'acanal', 'acaret', 'acat', 'acat', 'acatalpa', 'acatnip', 'acaw'])]

MyStackItem 类中的 PrintWords() 和 PrintStack() 方法生成相同的输出。使用我们之前的例子，在回溯单词 catalpa 后，在 Pop() 之前，堆栈看起来像这样：

[('aca', ['acanal', 'acaret'])], [('talpa', [])]

而在 search() 方法中的 Pop() 之后，talpa 已被移除，因为它没有匹配的单词，如空方括号（[]）所示。

[('aca', ['acanal', 'acaret'])]

运行时间

当我使用 npdict.txt 字典文件运行 Palindrome.exe 的 Release 版本时，以下是一些结果：

运行时	回文中的单词数
1 分钟	1129
2 分钟	4801
3 分钟	5406
15 分钟	6677
24 分钟	7003
27 分钟	7197
35 分钟	7456
4 小时	7649

结论

Python 是一种强大的语言，语法非常易读。虽然将其转换为 C# 是直接的，但 C# 版本却相当冗长，行数是 Python 的三倍多。使用我相当老旧的四核机器和 4 GB 的内存，我无法生成接近 Norvig 先生令人印象深刻的 21,000 字回文。如果 CodeProject 的读者能写一篇文章，介绍如何利用云计算的力量来利用更强大的硬件来运行这个程序，那将很有意思。

未来，我计划演示一个生成回文的“表亲”——字谜。字谜是通过重新排列另一个单词或短语的字母形成的，例如，“Old West Action”是“Clint Eastwood”的一个字谜。

版本 1.0.0.0