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.

Hi,

interesting code.

I learned a lot thanks.

Thanks for visiting jojosiao 😀