PHP Recursion – Cellphone Number Combination

Few days ago, a friend ask help for an obviously recursive problem. The problem was to give all letter combination for every given number in a typical cellphone number. Given a very limited time at work, I manage to solve this interesting problem.

The Problem

I don’t know how is this going to be applied to real world problem, but I give it a try anyway. A typical cellphone has number keys 1, 2 ,3 ,4 ,5 ,6 ,7 ,8 and 9. They omit the 0 part (I don’t know why). The program will accept any number key, ex: 23, and the program will output the letter combinations for 1 and 2 which are {abc} and {def}.

Number input: 23

Output:
ad
ae
af
bd
be
bf
cd
ce
cf

It simply distribute {abc} to {def} so that it will output any letter combination and good thing the problem does not require that letters can be interchange. It is only a one-way permutation.

Another example for a larger input:

Number input: 234

Output:
adg
adh
adi
aeg
aeh
aei
afg
afh
afi
bdg
bdh
bdi
beg
beh
bei
bfg
bfh
bfi
cdg
cdh
cdi
ceg
ceh
cei
cfg
cfh
cfi

Identifying the base problem

I’m not really good at recursion but I have learn a bit from it during college and occasionaly at work. This is what I see as the base problem. I hope I could draw an illustration but resources and time is a bit limited so here is the wordy illustration.

First, we group letters into number keys as an array something like below:

$digits = array(
    '1' => array('$','@','#'),
    '2' => array('a', 'b', 'c'),
    '3' => array('d','e','f'),
    '4' => array('g','h','i'),
    '5' => array('j','k','l'),
    '6' => array('m','n','o'),
    '7' => array('p','q','r','s'),
    '8' => array('t','u','v'),
    '9' => array('w','x','y','z')
);

Since the input are the number keys, then we say that for every input number, it is equivalent to an array of letters.

Second, we identify the base problem that supports our recursive solution. The pseudocode looks like this:

If there are no more group of letters then
    output the concatenated letters
Else
    For every given array of numbers containing letters
        get the first group of letters.
        For every letter in that first group of letters
            concatenate the previous letter to this letter
            process the remaining group of letters using the concatenated leters

The code

I’m not really good at explaining things so perhaps my code will explain the rest of it.

<?php

class CellPhone_Numbers {
    public $digits = array(
        '1' => array('$','@','#'),
        '2' => array('a', 'b', 'c'),
        '3' => array('d','e','f'),
        '4' => array('g','h','i'),
        '5' => array('j','k','l'),
        '6' => array('m','n','o'),
        '7' => array('p','q','r','s'),
        '8' => array('t','u','v'),
        '9' => array('w','x','y','z')
    );

    public $output = array();
    
    public function dissolve($prefix, array $other_digits = array())
    {
        if (empty($other_digits))
        {
            $this->output[] = $prefix;
        }
        else
        {
            $first_chunk = array_shift($other_digits);
            
            foreach ($first_chunk as $chunk_char)
            {
                $this->dissolve($prefix.$chunk_char, $other_digits);
            }
        }
    }

    public function run($numbers)
    {
        $numbers = str_split($numbers);
        $ret = array();

        foreach ($numbers as $index)
        {
            $ret[] = $this->digits[$index];
        }
        
        $this->dissolve('', $ret);
    }
}

$cp = new CellPhone_Numbers;
$cp->run('234');

var_dump($cp->output);

Enjoy.