算法问题:字母组合

Question

我正在尝试编写一段代码来执行以下操作:

取数字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,但任何一般提示都将受到高度赞赏.

更新:

更多背景知识:(非常感谢快速回复!)

我的问题背后的想法是构建一个脚本,帮助人们轻松地将他们想要记住的数字转换为更容易记住的单词.这有时被称为"伪数字学".

我希望脚本能够为我提供所有可能的组合,然后根据剥离的单词数据库进行组合.这些被删除的单词来自字典,并且我在我的问题中提到的所有字母都被删除了.这样,要编码的数字通常可以容易地与一个或多个数据库记录相关.当这种情况发生时,您最终会得到一个单词列表,您可以使用这些单词来记住您想要记住的数字.

Answer 1

它可以很容易地递归完成.

想法是要处理大小为n的整个代码,首先必须处理n - 1位数.一旦你得到了n-1个数字的所有答案,就可以通过向它们附加最后一个字符的正确字符来推断出整个答案.

Answer 2

您想要保存数字 -> 字母分配的一般结构是一个或多个数组，类似于：

// 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”作为分割字符串进行爆炸。