使用递归算法解决 Jumble 谜题
4.29/5 (3投票s)
使用递归、LINQ 和 COM 查找可从字符串派生的所有单词
引言
在最近的一篇文章《C# 中使用递归计算排列》中，我演示了如何使用递归算法计算给定项目集的所有排列。该算法是 Alexander Bogomolny 文章《计数和列出所有排列》中介绍的三种算法之一。这篇文章可以在互动数学杂集和谜题网站上找到。在这篇文章和配套的应用程序中，我将使用递归算法来创建一个单词解密器。基于对经典 Jumble 谜题的改编，用户输入一个由 2 到 7 个随机排序的字符组成的字符串。该应用程序将尝试通过推导出输入字符串的所有排列，然后在英语词典中搜索它们来“解密”该字符串。
请注意，您可以选择输入任何类型的字符——字母、数字或符号。所有唯一的排列都将被返回。但是，只有纯字符字符串才能被应用程序正确识别为已知单词。
背景
我们都曾在报纸上见过 Jumble 单词组合游戏。在线上也可以找到这个经典益智游戏的示例，网址是 UCLICKgames.com。组成单词的字母以随机顺序显示。目标是重新排列字母并找出隐藏的单词。Jumble 谜题通常只有一个正确答案。Jumble 谜题的难度通常从简单的四字母单词到更难解决的六字母单词不等。虽然四字母单词*只有* 120 种可能的排列，但六字母单词有六倍的可能排列（720 种），这使得它们更难解决。
该应用程序使用递归算法来解决这个谜题，这与我们解决它的方式非常相似。我们通常开始可视化或写下谜题中的字母组合，直到偶然发现一个可识别的单词。有时，我们“一眼”就看到了单词；其他时候，我们为答案苦苦挣扎。当然，有时答案会因为我们词汇量的限制而让我们难以捉摸。我们偶然发现一个单词，但由于我们不熟悉它，我们将其排除并继续进行排列。与我们不同，该应用程序可以快速搜索*整个*词典以查找所有可能的匹配项。
Using the Code
为了演示使用递归算法解密字符字符串，我创建了一个简单的 Windows 窗体应用程序。该应用程序使用 C# 3.0、Visual Studio 2008 和 .NET Framework 3.5 构建。它由一个 Windows 窗体和一个单独的小类文件组成，其中包含定义游戏逻辑的方法、字段和属性。如前所述，该应用程序使用 Bogomolny 的原始方法，这些方法已从 Java 转换为 C#。原始方法、字段和属性被重命名，以创建更具可读性、易于理解的 C# 代码。
下面是包含游戏逻辑的*Permutations.cs*类文件。实际源代码为每个方法都提供了完整的注释。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows.Forms;
[assembly: CLSCompliant(true)]
namespace Unscramble
{
class Permutations
{
private int itemLevel = -1;
private int numOfItems;
private int permCount;
private int[] permutation = new int[0];
private char[] inputCharSet;
private List<string> permList = new List<string>();
object missing = System.Reflection.Missing.Value;
// Called directly w/o using directive to prevent ambiguity
// with System.Windows.Forms.Application object
Microsoft.Office.Interop.Word.Application wordApp =
new Microsoft.Office.Interop.Word.Application();
ProgressBar pgProgress = (ProgressBar)Form1
.ActiveForm.Controls["pbProgress"];
public void MakeCharArray(string inputString)
{
inputCharSet = inputString.ToCharArray();
numOfItems = inputCharSet.Length;
Array.Resize(ref permutation, numOfItems);
}
public void Recursion(int position)
{
itemLevel++;
permutation.SetValue(itemLevel, position);
if(itemLevel == numOfItems)
{
AddPermutation(permutation);
}
else
{
for(int currentPosition = 0; currentPosition < numOfItems;
currentPosition++)
{
if(permutation[currentPosition] == 0)
{
Recursion(currentPosition);
}
}
}
itemLevel--;
permutation.SetValue(0, position);
}
private void AddPermutation(int[] currentPermutation)
{
string tempPermString = "";
foreach(int item in currentPermutation)
{
// Build string permutation from position permutation
tempPermString += inputCharSet.GetValue(item - 1);
}
permList.Add(tempPermString);
permCount++;
}
private bool CheckTheSpelling(string theWord)
{
pgProgress.Increment(1);
bool result = false;
try
{
if(wordApp.CheckSpelling(theWord, ref missing,
ref missing, ref missing, ref missing,
ref missing, ref missing, ref missing,
ref missing, ref missing, ref missing,
ref missing, ref missing) == true)
{
result = true;
}
else
{
result = false;
}
}
catch(Exception)
{
wordApp.Quit(ref missing, ref missing, ref missing);
}
return result;
}
public string OutputPermutations()
{
//Count all
int allPermCount = permList.Count();
var permListTrue = permList.Distinct();
//Count distinct
int uniquePermCount = permListTrue.Count();
pgProgress.Maximum = uniquePermCount;
permListTrue = permListTrue
.Where(perm => CheckTheSpelling(perm) == true)
.OrderBy(perm => perm);
var permListFalse = permList
.Distinct()
.Except(permListTrue)
.OrderBy(perm => perm);
//Count answers
int answersFound = permListTrue.Count();
StringBuilder tempDisplay = new StringBuilder();
try
{
foreach(string permutation in permListTrue)
{
tempDisplay.AppendLine(permutation + " (true)");
}
tempDisplay.AppendLine("-------------------");
foreach(string permutation in permListFalse)
{
tempDisplay.AppendLine(permutation + " (false)");
}
tempDisplay.AppendLine("-------------------");
tempDisplay.AppendLine("Total Permutations: " +
allPermCount.ToString());
tempDisplay.AppendLine("Unique Permutations: " +
uniquePermCount.ToString());
tempDisplay.AppendLine("Words Found: " + answersFound);
}
catch(Exception ex)
{
return ex.ToString();
}
finally
{
wordApp.Quit(ref missing, ref missing, ref missing);
}
return tempDisplay.ToString();
}
}
}
Microsoft Word 11.0 对象库
该应用程序使用 Microsoft Office Word 2003 的拼写检查功能来确定每个排列是否为公认的单词。我是通过向项目中添加对*Microsoft Word 11.0 Object Library*程序集的COM引用来实现的。如果您拥有 Microsoft Office Word 2007，则需要将 Microsoft Word 12.0 Object Library 程序集添加到您的项目中。使用 COM 或 Microsoft Word 不一定是最好或唯一的解决方案。还有其他应用程序和实用程序，包括免费软件，可以与该应用程序进行交互。另一种方法是使用 Web 服务。每个排列或一组排列都可以发送到一个远程 Web 服务，该服务将提供拼写检查。
为了最大限度地减少内存使用，该应用程序会创建一个 Word 应用程序接口（wordApp）的单个实例，以对每个单独的排列调用CheckSpelling(string theWord)方法。完成后或发生异常时，通过调用Quit()方法销毁wordApp对象。当wordApp正在处理排列时，您会在任务管理器“进程”选项卡中看到一个*WINWORD.EXE*实例正在运行。
解密过程
- 从用户输入的字符串构建一个字符数组（例如，
cdeo->{c, d, e, o}）。 - 使用递归算法根据字符的位置计算每个字符的排列（例如：
{1, 4, 2, 3}）。 - 通过将基于数字位置的排列与字符数组中的相应字符匹配来创建字符排列（例如，
{1, 4, 2, 3}->{c, o, d, e}）。 - 将字符排列存储在
List<string>对象中作为string（例如，{code}）。 - 从
List<string>中删除任何重复的排列。请参阅下面的解释。 - 使用 LINQ 的
Where()扩展将List<string>中的每个排列发送到CheckSpelling(string theWord)方法，该方法又会调用 Microsoft Word。 - 仅将
CheckSpelling(string theWord)方法返回布尔值为true的排列存储在第二个List<string>对象中，这表示该排列在 Word 的字典中找到。 （这些是正确的答案）。 - 向用户返回一个已排序的排列列表，将正确答案排在最前面。最后还包括了结果摘要。
递归算法的方法非常快，而将结果传递给 Word 对象进行拼写检查可能非常耗时。当 Word 正在拼写检查每个排列时，UI 底部的进度条会更新。在应用程序运行时，请务必不要切换窗口。
处理重复排列
与上一篇文章中的控制台应用程序不同，此 Windows 应用程序使用 LINQ 的 Distinct() 扩展来删除重复的排列。当输入字符串中存在相同字符时，会产生重复的排列。例如，“tester”一词有两个 t 和两个 e，这将在总共 720 种可能的排列中生成 540 种重复的排列。将现有 List<string> 中的排列使用 LINQ 的 Distinct() 扩展复制到第二个 List<string> 对象中，从而消除重复项。请参阅下面的示例，该示例为了显示目的已被缩短。
安装源代码
要使用源代码，请在 Microsoft Visual Studio 2008 中创建一个名为“Unscramble”的 Windows 窗体应用程序。用源代码的 Form1.cs 文件替换默认的 Form1.cs 文件。添加 Permutations.cs 类文件。最后，添加一个对 Microsoft Word 11.0 Object Library 程序集（Microsoft.Office.Interop.Word）的 COM 引用。这样做时，另外两个程序集 Microsoft.Vbe.Interop 和 Interop.Microsoft.Office.Core 将被自动添加到您项目的引用文件夹中。如果您实现了除 Word 之外的替代拼写检查方法，则需要修改 CheckTheSpelling(string) 方法。
历史
- 2009 年 6 月 28 日 - 版本 1.0
- 初始版本
- 2009 年 7 月 6 日 - 版本 1.1
- 重写了
OutputPermutations()方法，将正确答案排在前面，并提供更好的结果摘要 - 将最大输入
string长度从 6 个字符（720 种可能排列）更改为 7 个字符（5,040 种可能排列） - 更新了文章和文章的代码引用
- 重写了