算法问题：字母组合
我正在尝试编写一段代码来执行以下操作：
取数字0到9，并给该数字分配一个或者多个字母。例如：
0 = N, 1 = L, 2 = T, 3 = D, 4 = R, 5 = V or F, 6 = B or P, 7 = Z, 8 = H or CH or J, 9 = G
当我有0123这样的代码时，对它进行编码很容易。显然，它将组成代码NLTD。当引入5,6或者8之类的数字时，情况会有所不同。 051之类的数字可能会导致多种可能性：
NVL和NFL
显而易见，较长的数字甚至包括5、6或者8这样的数字，甚至会变得"更糟"。
由于对数学非常不好，我还无法提出一个体面的解决方案，该解决方案无法让我为程序提供大量数字，并吐出所有可能的字母组合。因此，我希望获得一些帮助，因为我似乎无法弄清楚。挖掘一些有关排列和组合的信息，但是没有运气。
感谢任何建议/提示。我需要编写代码的语言是PHP，但是任何常规提示将不胜感激。
更新：
其他背景：(非常感谢快速回复！)
我的问题背后的想法是构建一个脚本，该脚本人们轻松地将他们想记住的数字转换为更容易记住的单词。有时将其称为"伪命理学"。
我希望脚本能给我所有可能的组合，然后将其组合到剥离单词数据库中。这些被剥离的单词仅来自词典，而我在问题中提到的所有字母都被剥离了。这样，要编码的数字通常可以轻松地与一个或者多个数据库记录相关。发生这种情况时，我们最终会得到一个单词列表，可以用来记住要记住的数字。
解决方案
可以轻松地递归完成。
这个想法是要处理大小为n的整个代码，必须首先处理n个1位数。
一旦获得n-1位数字的所有答案，就可以通过将最后一个的正确字符添加到答案来推导出整个答案。
我们可以执行以下操作：
创建一个结果数组。
在数组中创建一个值为""的项目
循环浏览数字，例如051分别分析每个数字。
每次找到数字之间的1到1匹配项时，将正确的值添加到结果数组中的所有项目。
因此，""变为N。
每次找到1对多的匹配项时，请使用一个选项将新行添加到结果数组，并使用另一个选项更新现有结果。
因此N成为NV并创建了一个新项NF
那么最后一个数字是1对1的匹配项，因此结果数组中的项目变为
NVL和NFL
要产生结果，请循环遍历结果数组，打印结果或者进行其他操作。
假设pn是给定数字字符串s直至n位的所有可能字母组合的列表。
然后，以下算法将生成" pn + 1"：
digit = s[n+1];
foreach(letter l that digit maps to)
{
foreach(entry e in p(n))
{
newEntry = append l to e;
add newEntry to p(n+1);
}
}
第一次迭代有点特殊，因为p-1是不确定的。我们可以简单地将p0初始化为第一个字符的所有可能字符的列表。
因此，051示例：
迭代0：
p(0) = {N}
迭代1：
digit = 5
foreach({V, F})
{
foreach(p(0) = {N})
{
newEntry = N + V or N + F
p(1) = {NV, NF}
}
}
迭代2：
digit = 1
foreach({L})
{
foreach(p(1) = {NV, NF})
{
newEntry = NV + L or NF + L
p(2) = {NVL, NFL}
}
}
我们想要保留数字->字母分配的一般结构是一个或者多个数组，类似于：
// 0 = N, 1 = L, 2 = T, 3 = D, 4 = R, 5 = V or F, 6 = B or P, 7 = Z,
// 8 = H or CH or J, 9 = G
$numberMap = new Array (
0 => new Array("N"),
1 => new Array("L"),
2 => new Array("T"),
3 => new Array("D"),
4 => new Array("R"),
5 => new Array("V", "F"),
6 => new Array("B", "P"),
7 => new Array("Z"),
8 => new Array("H", "CH", "J"),
9 => new Array("G"),
);
然后，一些递归逻辑为我们提供了类似于以下功能：
function GetEncoding($number) {
$ret = new Array();
for ($i = 0; $i < strlen($number); $i++) {
// We're just translating here, nothing special.
// $var + 0 is a cheap way of forcing a variable to be numeric
$ret[] = $numberMap[$number[$i]+0];
}
}
function PrintEncoding($enc, $string = "") {
// If we're at the end of the line, then print!
if (count($enc) === 0) {
print $string."\n";
return;
}
// Otherwise, soldier on through the possible values.
// Grab the next 'letter' and cycle through the possibilities for it.
foreach ($enc[0] as $letter) {
// And call this function again with it!
PrintEncoding(array_slice($enc, 1), $string.$letter);
}
}
递归三声欢呼！这将通过以下方式使用：
PrintEncoding(GetEncoding("052384"));
而且，如果我们真的希望将其作为数组，则可以使用输出缓冲并使用" \ n"作为拆分字符串进行爆炸。
我们想要的表格可能是这样的：
function combinations( $str ){
$l = len( $str );
$results = array( );
if ($l == 0) { return $results; }
if ($l == 1)
{
foreach( $codes[ $str[0] ] as $code )
{
$results[] = $code;
}
return $results;
}
$cur = $str[0];
$combs = combinations( substr( $str, 1, $l ) );
foreach ($codes[ $cur ] as $code)
{
foreach ($combs as $comb)
{
$results[] = $code.$comb;
}
}
return $results;}
这很丑陋，pidgin-php，所以请先进行验证。基本思想是从[1..n]生成字符串的每个组合，然后在所有这些组合的前面添加str [0]的每个可能代码。请记住，在最坏的情况下，这将使字符串的长度成指数增长，因为编码方案中实际上存在很多歧义。
诀窍不仅在于生成与给定数字匹配的所有可能的字母组合，还在于选择最容易记住的字母序列。建议在每个序列上运行soundex算法，并尝试与英语词典(如Wordnet)匹配，以找到最"听起来实在"的序列。
这是Python中的递归解决方案。
#!/usr/bin/env/python
import sys
ENCODING = {'0':['N'],
'1':['L'],
'2':['T'],
'3':['D'],
'4':['R'],
'5':['V', 'F'],
'6':['B', 'P'],
'7':['Z'],
'8':['H', 'CH', 'J'],
'9':['G']
}
def decode(str):
if len(str) == 0:
return ''
elif len(str) == 1:
return ENCODING[str]
else:
result = []
for prefix in ENCODING[str[0]]:
result.extend([prefix + suffix for suffix in decode(str[1:])])
return result
if __name__ == '__main__':
print decode(sys.argv[1])
输出示例：
$ ./demo 1 ['L'] $ ./demo 051 ['NVL', 'NFL'] $ ./demo 0518 ['NVLH', 'NVLCH', 'NVLJ', 'NFLH', 'NFLCH', 'NFLJ']
这类问题通常可以通过递归来解决。在红宝石中，一种(快速而肮脏的)解决方案是
@values = Hash.new([])
@values["0"] = ["N"]
@values["1"] = ["L"]
@values["2"] = ["T"]
@values["3"] = ["D"]
@values["4"] = ["R"]
@values["5"] = ["V","F"]
@values["6"] = ["B","P"]
@values["7"] = ["Z"]
@values["8"] = ["H","CH","J"]
@values["9"] = ["G"]
def find_valid_combinations(buffer,number)
first_char = number.shift
@values[first_char].each do |key|
if(number.length == 0) then
puts buffer + key
else
find_valid_combinations(buffer + key,number.dup)
end
end
end
find_valid_combinations("",ARGV[0].split(""))
如果从命令行运行此命令，则会得到：
$ ruby r.rb 051 NVL NFL
这与暴力搜索和回溯有关
实际上，有一个比枚举数字的所有可能译文并查找它们更好的解决方案：只需对字典中的每个单词进行反向计算，然后将数字字符串存储在另一个字段中。因此，如果映射是：
0 = N, 1 = L, 2 = T, 3 = D, 4 = R, 5 = V or F, 6 = B or P, 7 = Z, 8 = H or CH or J, 9 = G
反向映射为：
N = 0, L = 1, T = 2, D = 3, R = 4, V = 5, F = 5, B = 6, P = 6, Z = 7, H = 8, J = 8, G = 9
请注意，" ch"没有映射，因为" c"将被删除，而" h"仍将转换为8.
然后，我们要做的就是遍历字典单词中的每个字母，如果匹配则输出适当的数字，如果不匹配则不执行任何操作。
将所有生成的数字字符串存储为数据库中的另一个字段。当我们要查找内容时，只需对输入的数字执行简单的查询，而不必进行数十(或者数百或者数千)个潜在单词的查找。
