Algorithm problem: letter combinations

Question

I'm trying to write a piece of code that will do the following:

Take the numbers 0 to 9 and assign one or more letters to this number. For example:

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

When I have a code like 0123, it's an easy job to encode it. It will obviously make up the code NLTD. When a number like 5,6 or 8 is introduced, things get different. A number like 051 would result in more than one possibility:

NVL and NFL

It should be obvious that this gets even "worse" with longer numbers that include several digits like 5,6 or 8.

Being pretty bad at mathematics, I have not yet been able to come up with a decent solution that will allow me to feed the program a bunch of numbers and have it spit out all the possible letter combinations. So I'd love some help with it, 'cause I can't seem to figure it out. Dug up some information about permutations and combinations, but no luck.

Thanks for any suggestions/clues. The language I need to write the code in is PHP, but any general hints would be highly appreciated.

Answer 1

It can be done easily recursively.

The idea is that to handle the whole code of size n, you must handle first the n - 1 digits. Once you have all answers for n-1 digits, the answers for the whole are deduced by appending to them the correct(s) char(s) for the last one.

Answer 2

Could you do the following: Create a results array. Create an item in the array with value ""

Loop through the numbers, say 051 analyzing each one individually.

Each time a 1 to 1 match between a number is found add the correct value to all items in the results array. So "" becomes N.

Each time a 1 to many match is found, add new rows to the results array with one option, and update the existing results with the other option. So N becomes NV and a new item is created NF

Then the last number is a 1 to 1 match so the items in the results array become NVL and NFL

To produce the results loop through the results array, printing them, or whatever.

Answer 3

Some more background: (and thanks a lot for the quick responses!)

The idea behind my question is to build a script that will help people to easily convert numbers they want to remember to words that are far more easily remembered. This is sometimes referred to as "pseudonumerology".

I want the script to give me all the possible combinations that are then held against a database of stripped words. These stripped words just come from a dictionary and have all the letters I mentioned in my question stripped out of them. That way, the number to be encoded can usually easily be related to a one or more database records. And when that happens, you end up with a list of words that you can use to remember the number you wanted to remember.

Thanks again for any more insights.

Answer 4

Let pn be a list of all possible letter combinations of a given number string s up to the nth digit.

Then, the following algorithm will generate 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);
    }
}

The first iteration is somewhat of a special case, since p_-1 is undefined. You can simply initialize p₀ as the list of all possible characters for the first character.

So, your 051 example:

Iteration 0:

p(0) = {N}

Iteration 1:

digit = 5
foreach({V, F})
{
    foreach(p(0) = {N})
    {
        newEntry = N + V  or  N + F
        p(1) = {NV, NF}
    }
}

Iteration 2:

digit = 1
foreach({L})
{
    foreach(p(1) = {NV, NF})
    {
        newEntry = NV + L  or  NF + L
        p(2) = {NVL, NFL}
    }
}

Answer 5

The general structure you want to hold your number -> letter assignments is an array or arrays, similar to:

// 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"),
);

Then, a bit of recursive logic gives us a function similar to:

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);
    }
}

Three cheers for recursion! This would be used via:

PrintEncoding(GetEncoding("052384"));

And if you really want it as an array, play with output buffering and explode using "\n" as your split string.

Answer 6

The form you want is probably something like:

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;}

This is ugly, pidgin-php so please verify it first. The basic idea is to generate every combination of the string from [1..n] and then prepend to the front of all those combinations each possible code for str[0]. Bear in mind that in the worst case this will have performance exponential in the length of your string, because that much ambiguity is actually present in your coding scheme.

Answer 7

The trick is not only to generate all possible letter combinations that match a given number, but to select the letter sequence that is most easy to remember. A suggestion would be to run the soundex algorithm on each of the sequence and try to match against an English language dictionary such as Wordnet to find the most 'real-word-sounding' sequences.

Answer 8

Here is a recursive solution in 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])

Example output:

$ ./demo 1
['L']
$ ./demo 051
['NVL', 'NFL']
$ ./demo 0518
['NVLH', 'NVLCH', 'NVLJ', 'NFLH', 'NFLCH', 'NFLJ']

Answer 9

This kind of problem are usually resolved with recursion. In ruby, one (quick and dirty) solution would be

@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(""))

And if you run this from the command line you will get:

$ ruby r.rb 051
NVL
NFL

This is related to brute-force search and backtracking

Answer 10

Thanks a million to all of you. Combining the insights you have given me I have now got a working solution. You people made my weekend.

Cheers!

Answer 11

There's actually a much better solution than enumerating all the possible translations of a number and looking them up: Simply do the reverse computation on every word in your dictionary, and store the string of digits in another field. So if your mapping is:

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

your reverse mapping is:

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

Note there's no mapping for 'ch', because the 'c' will be dropped, and the 'h' will be converted to 8 anyway. Then, all you have to do is iterate through each letter in the dictionary word, output the appropriate digit if there's a match, and do nothing if there isn't. Store all the generated digit strings as another field in the database. When you want to look something up, just perform a simple query for the number entered, instead of having to do tens (or hundreds, or thousands) of lookups of potential words.

Answer 12

Arachnid,

That is indeed a very nice approach that I will most certainly use for my own scheme. But since I want to present people with a general list of combinations for their own schemes, it would be undoable to use your method. Building up a new database for every possible scheme is something my web server certainly will not appreciate ;)

In the final version I will be using a database containing words with just the vowels stripped out (since nobody should be using those in their own scheme), so it's possible to come up with some general suggestions. In the end it will still be up to the creativity of the end user to come up with some usable results.

But great and useful thinking. Thanks a lot.

Answer 13

Hello,

I have a PHP script that creates all 4 letter combination with an array.

Check it out http://lxcblog.com/2010/10/27/create-four-4-letter-domain-name-password-key-combination-php-array-script/