试图用递归更优雅地解决电话词

Question

我已经查看了Stack Overflow，但没有找到任何工作。如果我错过了一个明显的帖子，我深表歉意。

我在学校遇到了一个问题，包括取一个电话号码，获取所有可能的单词组合，然后将其写入文本文件。我做到了，我的任务得到了充分的赞扬。我可以用七个嵌套的循环来完成这项工作，但这不是很优雅，也很僵硬。当我发现教科书上的解决方案是七个嵌套循环时，我大吃一惊，非常失望。我的教练也没有任何答案。

我尝试了很多不同的方法，但都没能接通。我确定了递归和终止点，但一直没能让它工作。我可以产生字母序列，但远没有达到应该有多少。我评论了我的尝试，这样你就可以看到我失败的思维过程：)请看一看，如果你有任何想法，请告诉我。

public partial class TelephoneWorderizer : Form
{
protected Dictionary<int, IEnumerable<string>> KeyMappings = new Dictionary<int, IEnumerable<string>>();
protected string[][] ActiveLettersGroups = null;
protected List<string> Words = new List<string>();
protected List<string> RecursiveWords = new List<string>();
protected int Iteration = 0;
public TelephoneWorderizer()
{
InitializeComponent();
this.KeyMappings = this.GetKeyMappings();
}
private void btnGetWords_Click(object sender, EventArgs e)
{
string textBoxContent = textBoxNumber.Text;
int[] digits = this.GetPhoneNumbers(textBoxContent);
List<string> words = this.GetWords(digits);
using (StreamWriter writer = new StreamWriter(@"E:words.txt"))
{
foreach (var word in words)
{
writer.WriteLine(word);
}
}
textBoxNumber.Clear();
}
private List<string> GetWords(int[] digits)
{
List<string[]> letterGroupings = new List<string[]>();
//digits array of numbers
for (int i = 0, j = digits.Length; i < j; i++)
{
int digit = digits[i];
//if the number has a letter group mapped to it
if (this.KeyMappings.ContainsKey(digit))
{
// letters mapped to a given number
letterGroupings.Add(this.KeyMappings[digit].ToArray());
}
}
this.WordMakerLoop(letterGroupings);
//this.WordMaker(letterGroupings);
return this.Words;
//return this.RecursiveWords;
}
//private void RecursionTest(string word, List<string[]> groups, int letterCtr, int groupCtr)
//{
//    string[] Group = groups[groupCtr];
//    word += Group[letterCtr];
//    letterCtr += 1;
//    if (letterCtr < Group.Length - 1)
//    {
//        letterCtr = 0;
//        groupCtr += 1;
//        // Hit bottom
//        if (groupCtr == groups.Count - 1)
//        {
//            groupCtr -= 1;
//        }
//        RecursionTest(word, groups, letterCtr, groupCtr);
//    }
//}
private void WordMaker(List<string[]> letterCollections)
{
string newword = "";
int numberLength = letterCollections.Count;
this.ActiveLettersGroups = letterCollections.ToArray();
string[] letterGroup = this.ActiveLettersGroups[0];
this.RecursiveGetWords(newword, 0, 0);
}
/// <summary>
/// 
/// </summary>
/// <param name="word"></param>
/// <param name="groupIndex"></param>
/// <param name="letterIndex"></param>
private void RecursiveGetWords(string word, int groupIndex, int letterIndex)
{
/*
* 
* 
* 
*/

var numActiveLetterGroups = this.ActiveLettersGroups.Length;
if (this.ActiveLettersGroups.Length > 0 && this.Iteration < numActiveLetterGroups)
{
if (groupIndex < numActiveLetterGroups)
{
var letters = this.ActiveLettersGroups[groupIndex]; // Picks the a letter group ex: A, B, C 
if (letterIndex < letters.Length)
{
//var letter1 = letters.Select(x => 
string letter = letters[letterIndex]; // Picks a letter from the group ex: A
word += letter;
this.RecursiveGetWords(word, groupIndex + 1, this.Iteration);
}
else
{
//this.RecursiveWords.Add(word);
//word = "";
//this.RecursiveGetWords(word, 0, 1);
}
}
else
{
this.RecursiveWords.Add(word);
word = "";
this.Iteration++;
this.RecursiveGetWords(word, 0, this.Iteration);
}
}
}
#region
private void WordMakerLoop(List<string[]> letterGroups)
{
string word = "";
// array of string[]
var newGroup = letterGroups.ToArray();
//grabs a letter group
for (int i = 0; i < newGroup.Length; i++)
{
var letterGroup1 = newGroup[i];
//grabs a letter from group 1
for (int j = 0; j < letterGroup1.Length; j++)
{
string letter1 = letterGroup1[j];
if (i + 1 < newGroup.Length)
{
var letterGroup2 = newGroup[i + 1];
//grabs a letter from group 2
for (int k = 0; k < letterGroup2.Length; k++)
{
string letter2 = letterGroup2[k];
if (i + 2 < newGroup.Length)
{
var letterGroup3 = newGroup[i + 2];
//grabs a letter from group 3
for (int l = 0; l < letterGroup3.Length; l++)
{
string letter3 = letterGroup3[l];
if (i + 3 < newGroup.Length)
{
var letterGroup4 = newGroup[i + 3];
//grabs a letter from group 4
for (int m = 0; m < letterGroup4.Length; m++)
{
string letter4 = letterGroup4[m];
if (i + 4 < newGroup.Length)
{
var letterGroup5 = newGroup[i + 4];
//grabs a letter from group 5
for (int n = 0; n < letterGroup5.Length; n++)
{
string letter5 = letterGroup5[n];
if (i + 5 < newGroup.Length)
{
var letterGroup6 = newGroup[i + 5];
//grabs a letter from group 6
for (int o = 0; o < letterGroup6.Length; o++)
{
string letter6 = letterGroup6[o];
if (i + 6 < newGroup.Length)
{
var letterGroup7 = newGroup[i + 6];
//grabs a letter from group 6
for (int p = 0; p < letterGroup7.Length; p++)
{
string letter7 = letterGroup7[p];
word = letter1 + letter2 + letter3 + letter4 + letter5 + letter6 + letter7;
this.Words.Add(word);
word = "";
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
// Sanitizes input text and converts the string into and arra of int
private int[] GetPhoneNumbers(string content)
{
int[] phoneNumbers = null;
string cleanString = this.SanitizeString(content);
int numbers;
if (Int32.TryParse(cleanString, out numbers))
{
//phoneNumbers = this.GetIntArray(numbers).OfType<int>().ToList();
phoneNumbers = this.GetIntArray(numbers);
}
return phoneNumbers;
}
// Removes potential unwanted characters from the phone number
private string SanitizeString(string content)
{
content = content.Replace("-", "");
content = content.Replace("(", "");
content = content.Replace(")", "");
return content;
}
//breaks a number into an array of its individual digits
private int[] GetIntArray(int num)
{
List<int> listOfInts = new List<int>();
while (num > 0)
{
listOfInts.Add(num % 10);
num = num / 10;
}
listOfInts.Reverse();
return listOfInts.ToArray();
}
//gets the mappings for the numerical values
private Dictionary<int, IEnumerable<string>> GetKeyMappings()
{
List<string> alphabet = new List<string>() { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z" };
Dictionary<int, IEnumerable<string>> mappings = new Dictionary<int, IEnumerable<string>>();
for (int i = 0; i < 10; i++)
{
string[] letters = null;
switch (i)
{
case 0:
case 1:
break;
case 2:
case 3:
case 4:
case 5:
case 6:
case 8:
letters = alphabet.Take(3).ToArray();
mappings.Add(i, letters);
alphabet.RemoveRange(0, 3);
break;
case 7:
case 9:
letters = alphabet.Take(4).ToArray();
mappings.Add(i, letters);
alphabet.RemoveRange(0, 4);
break;
default:
break;
}
}
return mappings;
}
#endregion
}

让我强调一下，对于那些有疑问的人来说，学校的作业已经结束了。我想做得更好，效率更高。如果有帮助的话，我可以在gitHub上发布我的项目。

Answer 1

我现在太懒了，不想写任何代码，但你绝对应该能够通过递归而不是七个嵌套循环来完成这项工作，事实上，你应该能够设计一个可以处理任意长度电话号码的方法。

基本的想法是，你可以设计一个递归方法，比如这样：

void recurse(String phone, int index, StringBuilder sb)
{
// Get the number at position phone[index]
// Loop through the possible letters for that particular number (eg. A, B, C):
// Add the letter to the StringBuilder
// Call recurse(phone, index + 1, sb)
// Subtract last letter from the StringBuilder
}

每次重复出现时，您都在处理下一个数字/字母位置。

当然，如果您遇到终止条件(sb length==phone length)，那么您只需将StringBuilder的当前值写入文件并返回，而不是递归。

希望这能有所帮助。

编辑：抽出时间实际编写一些代码。它真的很简单，不需要LINQ：

class Program
{
static Dictionary<Char, String> DigitMap = new Dictionary<Char, String>()
{
{'0', "0"},
{'1', "1"},
{'2', "ABC"},
{'3', "DEF"},
{'4', "GHI"},
{'5', "JKL"},
{'6', "MNO"},
{'7', "PQRS"},
{'8', "TUV"},
{'9', "WXYZ"}
};
static void Main(string[] args)
{
String phone = Regex.Replace("867-5309", "[^0-9]", "");
recurse(phone, 0, new StringBuilder());
}
static void recurse(String phone, int index, StringBuilder sb)
{
// Terminating condition
if (index == phone.Length)
{
Console.WriteLine(sb.ToString());
return;
}
// Get digit and letters string
Char digit = phone[index];
String letters = DigitMap[digit];
// Loop through all letter combinations for digit
foreach (Char c in letters)
{
sb.Append(c);
recurse(phone, index + 1, sb);
sb.Length -= 1;
}
}
}
}

在这段代码中(我制作了一个简单的控制台应用程序)，我只是将单词写入控制台，但您可以将字符串添加到数组中，也可以将它们写入磁盘。

Answer 2

我假设您可能希望将每个数字以及所有的普通字母映射，再加上0到+的映射，转换为自己的数字。所以我制作了这个字典来处理映射：

var map = new Dictionary<char, string>()
{
{ '0', "+0"},
{ '1', "1" },
{ '2', "2ABC"},
{ '3', "3DEF"},
{ '4', "4GHI"},
{ '5', "5JKL"},
{ '6', "6MNO"},
{ '7', "7PQRS"},
{ '8', "8TUV"},
{ '9', "9WXYZ"},
};

我的置换函数是这样的：

Func<IEnumerable<char>, IEnumerable<IEnumerable<char>>> permutate = null;
permutate = cs =>
{
var result = Enumerable.Empty<IEnumerable<char>>();
if (cs.Any())
{
result = map[cs.First()].Select(c => new [] { c });
if (cs.Skip(1).Any())
{
result =
from xs in result
from ys in permutate(cs.Skip(1))
select xs.Concat(ys);
}
}
return result;
};

就是这样。

你可以这样使用它：

var digits = "[phone]"
.Where(x => char.IsDigit(x));
var results =
permutate(digits)
.Select(x => new string(x.ToArray()));

结果是字符串列表，其中每个字符串都是输入数字的排列。

如果您不想将数字映射到数字，只需将它们从原始字典定义中删除即可，但必须为数字1保留一个字符才能工作。

让我知道这是否适合你。

Answer 3

下面是Java伪代码递归函数：

void recWords(String number, int ind, String buf, Collection<String> result){
if(ind==number.length()) {
result.add(buf);
} else {
for(char letter : lettersForNumber(number.charAt(ind)) {
recWords(number, ind+1, buf+letter, result);
}
}
}

在以C#编写上述内容并将其改编为您的代码后进行进一步练习：

1. 将buf从String更改为一个共享的StringBuilder
2. 然后将其封装到类中，并在递归中只传递ind，将其他作为类成员变量
3. 然后最后将递归转换为循环(提示：3个嵌套循环，其中一个内部循环的迭代次数将增加)

关于非递归版本，我想：它的效率会低于递归，但它有趣且值得作为练习进行编码的地方在于，它将是广度优先的，而这个递归版本是深度优先的。

Answer 4

这里有一个非递归解决方案，

• 给定一个数字，计算它的第一个单词
• 给定一个单词，"递增"它以找到下一个单词

public static class TelephoneFinder
{
static char[] firstDigits = new char[]
{ '0', '1', 'A', 'D', 'G', 'J', 'M', 'P', 'T', 'W' };
public static string First(string number)
{
char[] firstWord = new char[number.Length];
for (int i = 0; i < number.Length; i++)
{
var c = number.Substring(i, 1);
firstWord[i] = firstDigits[int.Parse(c)];
}
return new String(firstWord);
}
static Dictionary<char, char> rollovers = new Dictionary<char, char> { 
{ '1', '0' }, { '2', '1' }, { 'D', 'A' }, { 'G', 'D' }, { 'J', 'G' },
{ 'M', 'J' }, { 'P', 'M' }, { 'T', 'P' }, { 'W', 'T' }, { '[', 'W' } };
public static string Next(string current)
{
char[] chars = current.ToCharArray();
for (int i = chars.Length - 1; i >= 0; i--)
{
// Increment current character
chars[i] = (char)((int)chars[i] + 1);
if (rollovers.ContainsKey(chars[i]))
// Roll current character over
// Will then continue on to next character
chars[i] = rollovers[chars[i]];
else
// Finish loop with current string
return new String(chars);
}
// Rolled everything over - end of list of words
return null;
}
}

调用为例如

string word = TelephoneFinder.First("867");
while (!String.IsNullOrEmpty(word))
{
Console.WriteLine(word);
word = TelephoneFinder.Next(word);
}

它可能需要一些整理，但它是一个通用的非递归解决方案，可以进行修改以适用于类似的"交叉乘积"情况。

Answer 5

对不起大家。这是我的第一篇Stack Overflow帖子，当我的问题得到答案时，我正期待着一封电子邮件，但一直没有得到。我只是觉得我的问题被淹没在了堆栈溢出的深渊中。

和我一起工作的一组开发人员用大约5行代码就解决了这个问题。我目前似乎找不到解决方案，但我认为这与Enigmatity发布的内容非常接近。我确信我们使用了排列。我会寻找我们使用的解决方案。谢谢大家。