I just tried for my first programming interview and one of the questions was to write a program that given a 7 digit telephone number, could print all possible combinations of letters that each number could represent.
A second part of the question was like what about if this would have been a 12 digit international number? How would that effect your design.
I don't have the code that I wrote in the interview, but I got the impression he wasn't happy with it.
What is the best way to do this?
This question is related to
algorithm
language-agnostic
combinatorics
I've implemented a cache which helped to reduce number of recursions. This cache will avoid scanning of letters that it had already done for previous combinations. For one instance it was going for 120k loops, after cache implementation it got reduced to 40k.
private List<String> generateWords(String phoneNumber) {
List<String> words = new LinkedList<String>();
List<String> wordsCache = new LinkedList<String>();
this.generatePossibleWords("", phoneNumber, words, wordsCache);
return words;
}
private void generatePossibleWords(String prefix, String remainder,
List<String> words, List<String> wordsCache) {
int index = Integer.parseInt(remainder.substring(0, 1));
for (int i = 0; i < phoneKeyMapper.get(index).size(); i++) {
String mappedChar = phoneKeyMapper.get(index).get(i);
if (prefix.equals("") && !wordsCache.isEmpty()) {
for (String word : wordsCache) {
words.add(mappedChar + word);
}
} else {
if (remainder.length() == 1) {
String stringToBeAdded = prefix + mappedChar;
words.add(stringToBeAdded);
wordsCache.add(stringToBeAdded.substring(1));
LOGGER.finest("adding stringToBeAdded = " + stringToBeAdded.substring(1));
} else {
generatePossibleWords(prefix + mappedChar,
remainder.substring(1), words, wordsCache);
}
}
}
}
private void createPhoneNumberMapper() {
if (phoneKeyMapper == null) {
phoneKeyMapper = new ArrayList<>();
phoneKeyMapper.add(0, new ArrayList<String>());
phoneKeyMapper.add(1, new ArrayList<String>());
phoneKeyMapper.add(2, new ArrayList<String>());
phoneKeyMapper.get(2).add("A");
phoneKeyMapper.get(2).add("B");
phoneKeyMapper.get(2).add("C");
phoneKeyMapper.add(3, new ArrayList<String>());
phoneKeyMapper.get(3).add("D");
phoneKeyMapper.get(3).add("E");
phoneKeyMapper.get(3).add("F");
phoneKeyMapper.add(4, new ArrayList<String>());
phoneKeyMapper.get(4).add("G");
phoneKeyMapper.get(4).add("H");
phoneKeyMapper.get(4).add("I");
phoneKeyMapper.add(5, new ArrayList<String>());
phoneKeyMapper.get(5).add("J");
phoneKeyMapper.get(5).add("K");
phoneKeyMapper.get(5).add("L");
phoneKeyMapper.add(6, new ArrayList<String>());
phoneKeyMapper.get(6).add("M");
phoneKeyMapper.get(6).add("N");
phoneKeyMapper.get(6).add("O");
phoneKeyMapper.add(7, new ArrayList<String>());
phoneKeyMapper.get(7).add("P");
phoneKeyMapper.get(7).add("Q");
phoneKeyMapper.get(7).add("R");
phoneKeyMapper.get(7).add("S");
phoneKeyMapper.add(8, new ArrayList<String>());
phoneKeyMapper.get(8).add("T");
phoneKeyMapper.get(8).add("U");
phoneKeyMapper.get(8).add("V");
phoneKeyMapper.add(9, new ArrayList<String>());
phoneKeyMapper.get(9).add("W");
phoneKeyMapper.get(9).add("X");
phoneKeyMapper.get(9).add("Y");
phoneKeyMapper.get(9).add("Z");
}
}
/**
* Simple Java implementation without any input/error checking
* (expects all digits as input)
**/
public class PhoneSpeller
{
private static final char[][] _letters = new char[][]{
{'0'},
{'1'},
{'A', 'B', 'C'},
{'D', 'E', 'F'},
{'G', 'H', 'I'},
{'J', 'K', 'L'},
{'M', 'N', 'O'},
{'P', 'Q', 'R', 'S'},
{'T', 'U', 'V'},
{'W', 'X', 'Y', 'Z'}
};
public static void main(String[] args)
{
if (args.length != 1)
{
System.out.println("Please run again with your phone number (no dashes)");
System.exit(0);
}
recursive_phoneSpell(args[0], 0, new ArrayList<String>());
}
private static void recursive_phoneSpell(String arg, int index, List<String> results)
{
if (index == arg.length())
{
printResults(results);
return;
}
int num = Integer.parseInt(arg.charAt(index)+"");
if (index==0)
{
for (int j = 0; j<_letters[num].length; j++)
{
results.add(_letters[num][j]+"");
}
recursive_phoneSpell(arg, index+1, results);
}
else
{
List<String> combos = new ArrayList<String>();
for (int j = 0; j<_letters[num].length; j++)
{
for (String result : results)
{
combos.add(result+_letters[num][j]);
}
}
recursive_phoneSpell(arg, index+1, combos);
}
}
private static void printResults(List<String> results)
{
for (String result : results)
{
System.out.println(result);
}
}
}
During a job interview I received this question regarding creating an array of and printing out all possible letter combinations of a phone number. During the interview I received a whisper from my interviewer about recursion and how it can't be done using loops. Very unnatural for me to receive input from another programmer, I trusted his advice instead of my own tuition and proceeded to write up a sloppy recursion mess. It didn't go so well. Before receiving input, as I had never received this problem before, my brain was calculating up the underlying replicable mathematical formula. Whispers under my breath, "can't just multiply by three, some of them are four" as my mind started racing against a short clock thinking about one answer while beginning to write another. It was not until the end of the week I received my call to let me know the sad news. It was later that night I decided to see if it really is a recursion problem. Turns out for me it isn't.
My solution below is coded in PHP, is non-recursive, works with any length of input and I've even included some comments to help describe what my variables mean. Its my official and unchanging final answer to this question. I hope this helps somebody else in the future, please feel free to translate this into other languages.
Me method involves calculating the total number of combinations and creating a buffer large enough to hold every byte. The length of my buffer is the same length you would expect to receive from a working recursive algorithm. I make an array that contains the groups of letters that represent each number. My method primarily works because your combo total will always be divisible by the number of letters in the current group. If you can imagine in your head a vertical list of the output of this algorithm, or see the list vertically as opposed to a horizontally written list of the combinations, my algorithm will begin to make sense. This algorithm allows us to loop through each byte vertically from top to bottom starting from the left instead of horizontally left to right, and populate each byte individually without requiring recursion. I use the buffer as though its a byte array to save time and energy.
NON-RECURSIVE, ITERATIVE PHP
<?php
// Display all possible combinations of letters for each number.
$input = '23456789';
// ====================
if(!isset($input[0]))
die('Nothing to see here!');
$phone_letters = 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')
);
$groups = array();
$combos_total = 1;
$l = strlen($input);
for($i = 0; $i < $l; ++$i) {
$groups[] = $phone_letters[$input[$i]];
$combos_total *= count($phone_letters[$input[$i]]);
}
$count = $combos_total / count($groups[0]);
$combos = array_fill(0, $combos_total, str_repeat(chr(0), strlen($input)));
for(
$group = 0, // Index for the current group of letters.
$groups_count = count($groups), // Total number of letter groups.
$letters = count($groups[0]), // Total number of letters in the current group.
$width = $combos_total, // Number of bytes to repeat the current letter.
$repeat = 1; // Total number of times the group will repeat.
;
) {
for($byte = 0, $width /= $letters, $r = 0; $r < $repeat; ++$r)
for($l = 0; $l < $letters; ++$l)
for($w = 0; $w < $width; ++$w)
$combos[$byte++][$group] = $groups[$group][$l];
if(++$group < $groups_count) {
$repeat *= $letters;
$letters = count($groups[$group]);
}
else
break;
}
// ====================
if(is_array($combos)) {
print_r($combos);
echo 'Total combos:', count($combos), "\n";
}
else
echo 'No combos.', "\n";
echo 'Expected combos: ', $combos_total, "\n";
NON-RECURSIVE, NON-ITERATIVE, NO-BUFFER, THREAD FRIENDLY, MATH ONLY + NON-RECURSIVE, ITERATIVE PHP OBJECT USING MULTI-BASE BIG ENDIAN
While I was working on the new house the other day, I had a realisation that I could use the mathematics from my first function coupled with my knowledge of base to treat all possible letter combinations of my input as a multi-dimensional number.
My object provides the functions necessary to store a prefered combination into a database, convert letters and numbers if it were required, pick out a combination from anywhere in the combination space using a prefered combination or byte and it all plays very well with multi-threading.
That being said, using my object I can provide a second answer that uses base, no buffer, no iterations and most importantly no recursion.
<?php
class phone {
public static $letters = 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')
);
// Convert a letter into its respective number.
public static function letter_number($letter) {
if(!isset($letter[0]) || isset($letter[1]))
return false;
for($i = 2; $i < 10; ++$i)
if(in_array($letter, phone::$letters[$i], true))
return $i;
return false;
}
// Convert letters into their respective numbers.
public static function letters_numbers($letters) {
if(!isset($letters[0]))
return false;
$length = strlen($letters);
$numbers = str_repeat(chr(0), $length);
for($i = 0; $i < $length; ++$i) {
for($j = 2; $j < 10; ++$j) {
if(in_array($letters[$i], phone::$letters[$j], true)) {
$numbers[$i] = $j;
break;
}
}
}
return $numbers;
}
// Calculate the maximum number of combinations that could occur within a particular input size.
public static function combination_size($groups) {
return $groups <= 0 ? false : pow(4, $groups);
}
// Calculate the minimum bytes reqired to store a group using the current input.
public static function combination_bytes($groups) {
if($groups <= 0)
return false;
$size = $groups * 4;
$bytes = 0;
while($groups !== 0) {
$groups >> 8;
++$bytes;
}
return $bytes;
}
public $input = '';
public $input_len = 0;
public $combinations_total = 0;
public $combinations_length = 0;
private $iterations = array();
private $branches = array();
function __construct($number) {
if(!isset($number[0]))
return false;
$this->input = $number;
$input_len = strlen($number);
$combinations_total = 1;
for($i = 0; $i < $input_len; ++$i) {
$combinations_total *= count(phone::$letters[$number[$i]]);
}
$this->input_len = $input_len;
$this->combinations_total = $combinations_total;
$this->combinations_length = $combinations_total * $input_len;
for($i = 0; $i < $input_len; ++$i) {
$this->branches[] = $this->combination_branches($i);
$this->iterations[] = $this->combination_iteration($i);
}
}
// Calculate a particular combination in the combination space and return the details of that combination.
public function combination($combination) {
$position = $combination * $this->input_len;
if($position < 0 || $position >= $this->combinations_length)
return false;
$group = $position % $this->input_len;
$first = $position - $group;
$last = $first + $this->input_len - 1;
$combination = floor(($last + 1) / $this->input_len) - 1;
$bytes = str_repeat(chr(0), $this->input_len);
for($i = 0; $i < $this->input_len; ++$i)
$bytes[$i] = phone::$letters[$this->input[$i]][($combination / $this->branches[$i]) % count(phone::$letters[$this->input[$i]])];
return array(
'combination' => $combination,
'branches' => $this->branches[$group],
'iterations' => $this->iterations[$group],
'first' => $first,
'last' => $last,
'bytes' => $bytes
);
}
// Calculate a particular byte in the combination space and return the details of that byte.
public function combination_position($position) {
if($position < 0 || $position >= $this->combinations_length)
return false;
$group = $position % $this->input_len;
$group_count = count(phone::$letters[$this->input[$group]]);
$first = $position - $group;
$last = $first + $this->input_len - 1;
$combination = floor(($last + 1) / $this->input_len) - 1;
$index = ($combination / $this->branches[$group]) % $group_count;
$bytes = str_repeat(chr(0), $this->input_len);
for($i = 0; $i < $this->input_len; ++$i)
$bytes[$i] = phone::$letters[$this->input[$i]][($combination / $this->branches[$i]) % count(phone::$letters[$this->input[$i]])];
return array(
'position' => $position,
'combination' => $combination - 1,
'group' => $group,
'group_count' => $group_count,
'group_index' => $index,
'number' => $this->input[$group],
'branches' => $this->branches[$group],
'iterations' => $this->iterations[$group],
'first' => $first,
'last' => $last,
'byte' => phone::$letters[$this->input[$group]][$index],
'bytes' => $bytes
);
}
// Convert letters into a combination number using Multi-Base Big Endian.
public function combination_letters($letters) {
if(!isset($letters[$this->input_len - 1]) || isset($letters[$this->input_len]))
return false;
$combination = 0;
for($byte = 0; $byte < $this->input_len; ++$byte) {
$base = count(phone::$letters[$this->input[$byte]]);
$found = false;
for($value = 0; $value < $base; ++$value) {
if($letters[$byte] === phone::$letters[$this->input[$byte]][$value]) {
$combination += $value * $this->branches[$byte];
$found = true;
break;
}
}
if($found === false)
return false;
}
return $combination;
}
// Calculate the number of branches after a particular group.
public function combination_branches($group) {
if($group >= 0 && ++$group < $this->input_len) {
$branches = 1;
for($i = $group; $i < $this->input_len; ++$i)
$branches *= count(phone::$letters[$this->input[$i]]);
return $branches === 1 ? 1 : $branches;
}
elseif($group === $this->input_len)
return 1;
else
return false;
}
// Calculate the number of iterations before a particular group.
public function combination_iteration($group) {
if($group > 0 && $group < $this->input_len) {
$iterations = 1;
for($i = $group - 1; $i >= 0; --$i)
$iterations *= count(phone::$letters[$this->input[$i]]);
return $iterations;
}
elseif($group === 0)
return 1;
else
return false;
}
// Iterations, Outputs array of all combinations using a buffer.
public function combinations() {
$count = $this->combinations_total / count(phone::$letters[$this->input[0]]);
$combinations = array_fill(0, $this->combinations_total, str_repeat(chr(0), $this->input_len));
for(
$group = 0, // Index for the current group of letters.
$groups_count = $this->input_len, // Total number of letter groups.
$letters = count(phone::$letters[$this->input[0]]), // Total number of letters in the current group.
$width = $this->combinations_total, // Number of bytes to repeat the current letter.
$repeat = 1; // Total number of times the group will repeat.
;
) {
for($byte = 0, $width /= $letters, $r = 0; $r < $repeat; ++$r)
for($l = 0; $l < $letters; ++$l)
for($w = 0; $w < $width; ++$w)
$combinations[$byte++][$group] = phone::$letters[$this->input[$group]][$l];
if(++$group < $groups_count) {
$repeat *= $letters;
$letters = count(phone::$letters[$this->input[$group]]);
}
else
break;
}
return $combinations;
}
}
// ====================
$phone = new phone('23456789');
print_r($phone);
//print_r($phone->combinations());
for($i = 0; $i < $phone->combinations_total; ++$i) {
echo $i, ': ', $phone->combination($i)['bytes'], "\n";
}
static final String[] keypad = {"", "", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"};
String[] printAlphabet(int num){
if (num >= 0 && num < 10){
String[] retStr;
if (num == 0 || num ==1){
retStr = new String[]{""};
} else {
retStr = new String[keypad[num].length()];
for (int i = 0 ; i < keypad[num].length(); i++){
retStr[i] = String.valueOf(keypad[num].charAt(i));
}
}
return retStr;
}
String[] nxtStr = printAlphabet(num/10);
int digit = num % 10;
String[] curStr = null;
if(digit == 0 || digit == 1){
curStr = new String[]{""};
} else {
curStr = new String[keypad[digit].length()];
for (int i = 0; i < keypad[digit].length(); i++){
curStr[i] = String.valueOf(keypad[digit].charAt(i));
}
}
String[] result = new String[curStr.length * nxtStr.length];
int k=0;
for (String cStr : curStr){
for (String nStr : nxtStr){
result[k++] = nStr + cStr;
}
}
return result;
}
This approach uses R and is based on first converting the dictionary to its corresponding digit representation, then using this as a look-up.
The conversion only takes 1 second on my machine (converting from the native Unix dictionary of about 100,000 words), and typical look-ups of up to 100 different digit inputs take a total of .1 seconds:
library(data.table)
#example dictionary
dict.orig = tolower(readLines("/usr/share/dict/american-english"))
#split each word into its constituent letters
#words shorter than the longest padded with "" for simpler retrieval
dictDT = setDT(tstrsplit(dict.orig, split = "", fill = ""))
#lookup table for conversion
#NB: the following are found in the dictionary and would need
# to be handled separately -- ignoring here
# (accents should just be appended to
# matches for unaccented version):
# c("", "'", "á", "â", "å", "ä",
# "ç", "é", "è", "ê", "í", "ñ",
# "ó", "ô", "ö", "û", "ü")
lookup = data.table(num = c(rep('2', 3), rep('3', 3), rep('4', 3),
rep('5', 3), rep('6', 3), rep('7', 4),
rep('8', 3), rep('9', 4)),
let = letters)
#using the lookup table, convert to numeric
for (col in names(dictDT)) {
dictDT[lookup, (col) := i.num, on = setNames("let", col)]
}
#back to character vector
dict.num = do.call(paste0, dictDT)
#sort both for faster vector search
idx = order(dict.num)
dict.num = dict.num[idx]
dict.orig = dict.orig[idx]
possibilities = function(input) dict.orig[dict.num == input]
#sample output:
possibilities('269')
# [1] "amy" "bmw" "cox" "coy" "any" "bow" "box" "boy" "cow" "cox" "coy"
possibilities('22737')
# [1] "acres" "bards" "barer" "bares" "barfs" "baser" "bases" "caper"
# [9] "capes" "cards" "cares" "cases"
The obvious solution is a function to map a digit to a list of keys, and then a function that would generate the possible combinations:
The first is obvious, the second is more problematic because you have around 3^number of digits combinations, which can be a very large number.
One way to do it is to look at each possibility for digit matching as a digit in a number (on base 4) and implement something close to a counter (jumping over some instances, since there are usually less than 4 letters mappable to a digit).
The more obvious solutions would be nested loops or recursion, which are both less elegant, but in my opinion valid.
Another thing for which care must be taken is to avoid scalability issues (e.g. keeping the possibilities in memory, etc.) since we are talking about a lot of combinations.
P.S. Another interesting extension of the question would be localization.
This is a recursive algorithm in C++11.
#include <iostream>
#include <array>
#include <list>
std::array<std::string, 10> pm = {
"0", "1", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"
};
void generate_mnemonic(const std::string& numbers, size_t i, std::string& m,
std::list<std::string>& mnemonics)
{
// Base case
if (numbers.size() == i) {
mnemonics.push_back(m);
return;
}
for (char c : pm[numbers[i] - '0']) {
m[i] = c;
generate_mnemonic(numbers, i + 1, m, mnemonics);
}
}
std::list<std::string> phone_number_mnemonics(const std::string& numbers)
{
std::list<std::string> mnemonics;
std::string m(numbers.size(), 0);
generate_mnemonic(numbers, 0, m, mnemonics);
return mnemonics;
}
int main() {
std::list<std::string> result = phone_number_mnemonics("2276696");
for (const std::string& s : result) {
std::cout << s << std::endl;
}
return 0;
}
private List<string> strs = new List<string>();
char[] numbersArray;
private int End = 0;
private int numberOfStrings;
private void PrintLetters(string numbers)
{
this.End = numbers.Length;
this.numbersArray = numbers.ToCharArray();
this.PrintAllCombinations(this.GetCharacters(this.numbersArray[0]), string.Empty, 0);
}
private void PrintAllCombinations(char[] letters, string output, int depth)
{
depth++;
for (int i = 0; i < letters.Length; i++)
{
if (depth != this.End)
{
output += letters[i];
this.PrintAllCombinations(this.GetCharacters(Convert.ToChar(this.numbersArray[depth])), output, depth);
output = output.Substring(0, output.Length - 1);
}
else
{
Console.WriteLine(output + letters[i] + (++numberOfStrings));
}
}
}
private char[] GetCharacters(char x)
{
char[] arr;
switch (x)
{
case '0': arr = new char[1] { '.' };
return arr;
case '1': arr = new char[1] { '.' };
return arr;
case '2': arr = new char[3] { 'a', 'b', 'c' };
return arr;
case '3': arr = new char[3] { 'd', 'e', 'f' };
return arr;
case '4': arr = new char[3] { 'g', 'h', 'i' };
return arr;
case '5': arr = new char[3] { 'j', 'k', 'l' };
return arr;
case '6': arr = new char[3] { 'm', 'n', 'o' };
return arr;
case '7': arr = new char[4] { 'p', 'q', 'r', 's' };
return arr;
case '8': arr = new char[3] { 't', 'u', 'v' };
return arr;
case '9': arr = new char[4] { 'w', 'x', 'y', 'z' };
return arr;
default: return null;
}
}
A Python solution is quite economical, and because it uses generators is efficient in terms of memory use.
import itertools
keys = dict(enumerate('::ABC:DEF:GHI:JKL:MNO:PQRS:TUV:WXYZ'.split(':')))
def words(number):
digits = map(int, str(number))
for ls in itertools.product(*map(keys.get, digits)):
yield ''.join(ls)
for w in words(258):
print w
Obviously itertools.product is solving most of the problem for you. But writing it oneself is not difficult. Here's a solution in go, which is careful to re-use the array result to generate all solutions in, and a closure f to capture the generated words. Combined, these give O(log n) memory use inside product.
package main
import (
"bytes"
"fmt"
"strconv"
)
func product(choices [][]byte, result []byte, i int, f func([]byte)) {
if i == len(result) {
f(result)
return
}
for _, c := range choices[i] {
result[i] = c
product(choices, result, i+1, f)
}
}
var keys = bytes.Split([]byte("::ABC:DEF:GHI:JKL:MNO:PQRS:TUV:WXYZ"), []byte(":"))
func words(num int, f func([]byte)) {
ch := [][]byte{}
for _, b := range strconv.Itoa(num) {
ch = append(ch, keys[b-'0'])
}
product(ch, make([]byte, len(ch)), 0, f)
}
func main() {
words(256, func(b []byte) { fmt.Println(string(b)) })
}
In Java using recursion:
import java.util.LinkedList;
import java.util.List;
public class Main {
// Number-to-letter mappings in order from zero to nine
public static String mappings[][] = {
{"0"}, {"1"}, {"A", "B", "C"}, {"D", "E", "F"}, {"G", "H", "I"},
{"J", "K", "L"}, {"M", "N", "O"}, {"P", "Q", "R", "S"},
{"T", "U", "V"}, {"W", "X", "Y", "Z"}
};
public static void generateCombosHelper(List<String> combos,
String prefix, String remaining) {
// The current digit we are working with
int digit = Integer.parseInt(remaining.substring(0, 1));
if (remaining.length() == 1) {
// We have reached the last digit in the phone number, so add
// all possible prefix-digit combinations to the list
for (int i = 0; i < mappings[digit].length; i++) {
combos.add(prefix + mappings[digit][i]);
}
} else {
// Recursively call this method with each possible new
// prefix and the remaining part of the phone number.
for (int i = 0; i < mappings[digit].length; i++) {
generateCombosHelper(combos, prefix + mappings[digit][i],
remaining.substring(1));
}
}
}
public static List<String> generateCombos(String phoneNumber) {
// This will hold the final list of combinations
List<String> combos = new LinkedList<String>();
// Call the helper method with an empty prefix and the entire
// phone number as the remaining part.
generateCombosHelper(combos, "", phoneNumber);
return combos;
}
public static void main(String[] args) {
String phone = "3456789";
List<String> combos = generateCombos(phone);
for (String s : combos) {
System.out.println(s);
}
}
}
An R solution using nested loops:
# Create phone pad
two <- c("A", "B", "C")
three <- c("D", "E", "F")
four <- c("G", "H", "I")
five <- c("J", "K", "L")
six <- c("M", "N", "O", "P")
seven <- c("Q", "R", "S")
eight <- c("T", "U", "V")
nine <- c("W", "X", "Y", "Z")
# Choose three numbers
number_1 <- two
number_2 <- three
number_3 <- six
# create an object to save the combinations to
combinations <- NULL
# Loop through the letters in number_1
for(i in number_1){
# Loop through the letters in number_2
for(j in number_2){
# Loop through the letters in number_3
for(k in number_3){
# Add each of the letters to the combinations object
combinations <- c(combinations, paste0(i, j, k))
}
}
}
# Print all of the possible combinations
combinations
I posted another, more bizarre R solution using more loops and sampling on my blog.
In numeric keyboards, texts and numbers are placed on the same key. For example 2 has “ABC” if we wanted to write anything starting with ‘A’ we need to type key 2 once. If we wanted to type ‘B’, press key 2 twice and thrice for typing ‘C’. below is picture of such keypad.
keypad http://d2o58evtke57tz.cloudfront.net/wp-content/uploads/phoneKeyboard.png
Given a keypad as shown in diagram, and a n digit number, list all words which are possible by pressing these numbers.
For example if input number is 234, possible words which can be formed are (Alphabetical order): 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
Let’s do some calculations first. How many words are possible with seven digits with each digit representing n letters? For first digit we have at most four choices, and for each choice for first letter, we have at most four choices for second digit and so on. So it’s simple maths it will be O(4^n). Since keys 0 and 1 don’t have any corresponding alphabet and many characters have 3 characters, 4^n would be the upper bound of number of words and not the minimum words.
Now let’s do some examples.
For number above 234. Do you see any pattern? Yes, we notice that the last character always either G,H or I and whenever it resets its value from I to G, the digit at the left of it gets changed. Similarly whenever the second last alphabet resets its value, the third last alphabet gets changes and so on. First character resets only once when we have generated all words. This can be looked from other end also. That is to say whenever character at position i changes, character at position i+1 goes through all possible characters and it creates ripple effect till we reach at end. Since 0 and 1 don’t have any characters associated with them. we should break as there will no iteration for these digits.
Let’s take the second approach as it will be easy to implement it using recursion. We go till the end and come back one by one. Perfect condition for recursion. let’s search for base case. When we reach at the last character, we print the word with all possible characters for last digit and return. Simple base case.When we reach at the last character, we print the word with all possible characters for last digit and return. Simple base case.
Following is C implementation of recursive approach to print all possible word corresponding to a n digit input number. Note that input number is represented as an array to simplify the code.
#include <stdio.h>
#include <string.h>
// hashTable[i] stores all characters that correspond to digit i in phone
const char hashTable[10][5] = {"", "", "abc", "def", "ghi", "jkl",
"mno", "pqrs", "tuv", "wxyz"};
// A recursive function to print all possible words that can be obtained
// by input number[] of size n. The output words are one by one stored
// in output[]
void printWordsUtil(int number[], int curr_digit, char output[], int n)
{
// Base case, if current output word is prepared
int i;
if (curr_digit == n)
{
printf("%s ", output);
return ;
}
// Try all 3 possible characters for current digir in number[]
// and recur for remaining digits
for (i=0; i<strlen(hashTable[number[curr_digit]]); i++)
{
output[curr_digit] = hashTable[number[curr_digit]][i];
printWordsUtil(number, curr_digit+1, output, n);
if (number[curr_digit] == 0 || number[curr_digit] == 1)
return;
}
}
// A wrapper over printWordsUtil(). It creates an output array and
// calls printWordsUtil()
void printWords(int number[], int n)
{
char result[n+1];
result[n] ='\0';
printWordsUtil(number, 0, result, n);
}
//Driver program
int main(void)
{
int number[] = {2, 3, 4};
int n = sizeof(number)/sizeof(number[0]);
printWords(number, n);
return 0;
}
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
Time Complexity:
Time complexity of above code is O(4^n) where n is number of digits in input number.
References:
Here is the working code for the same.. its a recursion on each step checking possibility of each combinations on occurrence of same digit in a series....I am not sure if there is any better solution then this from complexity point of view.....
Please let me know for any issues....
import java.util.ArrayList;
public class phonenumbers {
/**
* @param args
*/
public static String mappings[][] = {
{"0"}, {"1"}, {"A", "B", "C"}, {"D", "E", "F"}, {"G", "H", "I"},
{"J", "K", "L"}, {"M", "N", "O"}, {"P", "Q", "R", "S"},
{"T", "U", "V"}, {"W", "X", "Y", "Z"}
};
public static void main(String[] args) {
// TODO Auto-generated method stub
String phone = "3333456789";
ArrayList<String> list= generateAllnums(phone,"",0);
}
private static ArrayList<String> generateAllnums(String phone,String sofar,int j) {
// TODO Auto-generated method stub
//System.out.println(phone);
if(phone.isEmpty()){
System.out.println(sofar);
for(int k1=0;k1<sofar.length();k1++){
int m=sofar.toLowerCase().charAt(k1)-48;
if(m==-16)
continue;
int i=k1;
while(true && i<sofar.length()-2){
if(sofar.charAt(i+1)==' ')
break;
else if(sofar.charAt(i+1)==sofar.charAt(k1)){
i++;
}else{
break;
}
}
i=i-k1;
//System.out.print(" " + m +", " + i + " ");
System.out.print(mappings[m][i%3]);
k1=k1+i;
}
System.out.println();
return null;
}
int num= phone.charAt(j);
int k=0;
for(int i=j+1;i<phone.length();i++){
if(phone.charAt(i)==num){
k++;
}
}
if(k!=0){
int p=0;
ArrayList<String> list2= generateAllnums(phone.substring(p+1), sofar+phone.charAt(p)+ " ", 0);
ArrayList<String> list3= generateAllnums(phone.substring(p+1), sofar+phone.charAt(p), 0);
}
else{
ArrayList<String> list1= generateAllnums(phone.substring(1), sofar+phone.charAt(0), 0);
}
return null;
}
}
Use a list L where L[i] = the symbols that digit i can represent.
L[1] = @,.,! (for example) L[2] = a,b,c
Etc.
Then you can do something like this (pseudo-C):
void f(int k, int st[])
{
if ( k > numberOfDigits )
{
print contents of st[];
return;
}
for each character c in L[Digit At Position k]
{
st[k] = c;
f(k + 1, st);
}
}
Assuming each list contains 3 characters, we have 3^7 possibilities for 7 digits and 3^12 for 12, which isn't that many. If you need all combinations, I don't see a much better way. You can avoid recursion and whatnot, but you're not going to get something a lot faster than this no matter what.
It is similar to a question called letter combinations of a phone number,
here is my solution.
It works for an arbitrary number of digits, so long as the result doesn't exceed the memory limit.
import java.util.HashMap;
public class Solution {
public ArrayList<String> letterCombinations(String digits) {
ArrayList<String> res = new ArrayList<String>();
ArrayList<String> preres = new ArrayList<String>();
res.add("");
for(int i = 0; i < digits.length(); i++) {
String letters = map.get(digits.charAt(i));
if (letters.length() == 0)
continue;
for(String str : res) {
for(int j = 0; j < letters.length(); j++)
preres.add(str + letters.charAt(j));
}
res = preres;
preres = new ArrayList<String>();
}
return res;
}
static final HashMap<Character,String> map = new HashMap<Character,String>(){{
put('1', "");
put('2',"abc");
put('3',"def");
put('4',"ghi");
put('5',"jkl");
put('6',"mno");
put('7',"pqrs");
put('8',"tuv");
put('9',"wxyz");
put('0', "");
}} ;
}
I'm not sure how 12-digit international numbers affect the design.
Edit: International numbers will also be handled
This is the C# port of this answer.
Code
public class LetterCombinations
{
private static readonly Dictionary<string, string> Representations = new Dictionary<string, string>
{
{"2", "abc" },
{"3", "def" },
{"4", "ghi" },
{"5", "jkl" },
{"6", "mno" },
{"7", "pqrs" },
{"8", "tuv" },
{"9", "wxyz" },
};
public static List<string> FromPhoneNumber(string phoneNumber)
{
var result = new List<string> { string.Empty };
// go through each number in the phone
for (int i = 0; i < phoneNumber.Length; i++)
{
var pre = new List<string>();
foreach (var str in result)
{
var letters = Representations[phoneNumber[i].ToString()];
// go through each representation of the number
for (int j = 0; j < letters.Length; j++)
{
pre.Add(str + letters[j]);
}
}
result = pre;
}
return result;
}
}
Unit Tests
public class UnitTest
{
[TestMethod]
public void One_Digit_Yields_Three_Representations()
{
var sut = "2";
var expected = new List<string>{ "a", "b", "c" };
var actualResults = LetterCombinations.FromPhoneNumber(sut);
CollectionAssert.AreEqual(expected, actualResults);
}
[TestMethod]
public void Two_Digits_Yield_Nine_Representations()
{
var sut = "22";
var expected = new List<string> { "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc" };
var actualResults = LetterCombinations.FromPhoneNumber(sut);
CollectionAssert.AreEqual(expected, actualResults);
}
[TestMethod]
public void Three_Digits_Yield_ThirtyNine_Representations()
{
var sut = "222";
var actualResults = LetterCombinations.FromPhoneNumber(sut);
var possibleCombinations = Math.Pow(3,3); //27
Assert.AreEqual(possibleCombinations, actualResults.Count);
}
}
In JavaScript. A CustomCounter class takes care of incrementing indexes. Then just output the different possible combinations.
var CustomCounter = function(min, max) {
this.min = min.slice(0)
this.max = max.slice(0)
this.curr = this.min.slice(0)
this.length = this.min.length
}
CustomCounter.prototype.increment = function() {
for (var i = this.length - 1, ii = 0; i >= ii; i--) {
this.curr[i] += 1
if (this.curr[i] > this.max[i]) {
this.curr[i] = 0
} else {
break
}
}
}
CustomCounter.prototype.is_max = function() {
for (var i = 0, ii = this.length; i < ii; ++i) {
if (this.curr[i] !== this.max[i]) {
return false
}
}
return true
}
var PhoneNumber = function(phone_number) {
this.phone_number = phone_number
this.combinations = []
}
PhoneNumber.number_to_combinations = {
1: ['1']
, 2: ['2', 'a', 'b', 'c']
, 3: ['3', 'd', 'e', 'f']
, 4: ['4', 'g', 'h', 'i']
, 5: ['5', 'j', 'k', 'l']
, 6: ['6', 'm', 'n', 'o']
, 7: ['7', 'p', 'q', 'r', 's']
, 8: ['8', 't', 'u', 'v']
, 9: ['9', 'w', 'x', 'y', 'z']
, 0: ['0', '+']
}
PhoneNumber.prototype.get_combination_by_digit = function(digit) {
return PhoneNumber.number_to_combinations[digit]
}
PhoneNumber.prototype.add_combination_by_indexes = function(indexes) {
var combination = ''
for (var i = 0, ii = indexes.length; i < ii; ++i) {
var phone_number_digit = this.phone_number[i]
combination += this.get_combination_by_digit(phone_number_digit)[indexes[i]]
}
this.combinations.push(combination)
}
PhoneNumber.prototype.update_combinations = function() {
var min_indexes = []
, max_indexes = []
for (var i = 0, ii = this.phone_number.length; i < ii; ++i) {
var digit = this.phone_number[i]
min_indexes.push(0)
max_indexes.push(this.get_combination_by_digit(digit).length - 1)
}
var c = new CustomCounter(min_indexes, max_indexes)
while(true) {
this.add_combination_by_indexes(c.curr)
c.increment()
if (c.is_max()) {
this.add_combination_by_indexes(c.curr)
break
}
}
}
var phone_number = new PhoneNumber('120')
phone_number.update_combinations()
console.log(phone_number.combinations)
Scala solution:
def mnemonics(phoneNum: String, dict: IndexedSeq[String]): Iterable[String] = {
def mnemonics(d: Int, prefix: String): Seq[String] = {
if (d >= phoneNum.length) {
Seq(prefix)
} else {
for {
ch <- dict(phoneNum.charAt(d).asDigit)
num <- mnemonics(d + 1, s"$prefix$ch")
} yield num
}
}
mnemonics(0, "")
}
Assuming each digit maps to at most 4 characters, the number of recursive calls T satisfy the inequality T(n) <= 4T(n-1), which is of the order 4^n.
One option in Objective-C:
- (NSArray *)lettersForNumber:(NSNumber *)number {
switch ([number intValue]) {
case 2:
return @[@"A",@"B",@"C"];
case 3:
return @[@"D",@"E",@"F"];
case 4:
return @[@"G",@"H",@"I"];
case 5:
return @[@"J",@"K",@"L"];
case 6:
return @[@"M",@"N",@"O"];
case 7:
return @[@"P",@"Q",@"R",@"S"];
case 8:
return @[@"T",@"U",@"V"];
case 9:
return @[@"W",@"X",@"Y",@"Z"];
default:
return nil;
}
}
- (NSArray *)letterCombinationsForNumbers:(NSArray *)numbers {
NSMutableArray *combinations = [[NSMutableArray alloc] initWithObjects:@"", nil];
for (NSNumber *number in numbers) {
NSArray *lettersNumber = [self lettersForNumber:number];
//Ignore numbers that don't have associated letters
if (lettersNumber.count == 0) {
continue;
}
NSMutableArray *currentCombinations = [combinations mutableCopy];
combinations = [[NSMutableArray alloc] init];
for (NSString *letter in lettersNumber) {
for (NSString *letterInResult in currentCombinations) {
NSString *newString = [NSString stringWithFormat:@"%@%@", letterInResult, letter];
[combinations addObject:newString];
}
}
}
return combinations;
}
public class Permutation {
//display all combination attached to a 3 digit number
public static void main(String ar[]){
char data[][]= new char[][]{{'a','k','u'},
{'b','l','v'},
{'c','m','w'},
{'d','n','x'},
{'e','o','y'},
{'f','p','z'},
{'g','q','0'},
{'h','r','0'},
{'i','s','0'},
{'j','t','0'}};
int num1, num2, num3=0;
char tempdata[][]= new char[3][3];
StringBuilder number = new StringBuilder("324"); // a 3 digit number
//copy data to a tempdata array-------------------
num1= Integer.parseInt(number.substring(0,1));
tempdata[0] = data[num1];
num2= Integer.parseInt(number.substring(1,2));
tempdata[1] = data[num2];
num3= Integer.parseInt(number.substring(2,3));
tempdata[2] = data[num3];
//display all combinations--------------------
char temp2[][]=tempdata;
char tempd, tempd2;
int i,i2, i3=0;
for(i=0;i<3;i++){
tempd = temp2[0][i];
for (i2=0;i2<3;i2++){
tempd2 = temp2[1][i2];
for(i3=0;i3<3;i3++){
System.out.print(tempd);
System.out.print(tempd2);
System.out.print(temp2[2][i3]);
System.out.println();
}//for i3
}//for i2
}
}
}//end of class
I rewrote the latest answer to this (referred above) , from C to Java. I also included the support for 0 and 1 (as 0 and 1) because numbers such as 555-5055 weren't working at all with the above code.
Here it is. Some comments are preserved.
public static void printPhoneWords(int[] number) {
char[] output = new char[number.length];
printWordsUtil(number,0,output);
}
static String[] phoneKeys= new String[]{"0", "1", "ABC", "DEF", "GHI", "JKL",
"MNO", "PQRS", "TUV", "WXYZ"};
private static void printWordsUtil(int[] number, int curDigIndex, char[] output) {
// Base case, if current output word is done
if (curDigIndex == output.length) {
System.out.print(String.valueOf(output) + " ");
return;
}
// Try all 3-4 possible characters for the current digit in number[]
// and recurse for the remaining digits
char curPhoneKey[] = phoneKeys[number[curDigIndex]].toCharArray();
for (int i = 0; i< curPhoneKey.length ; i++) {
output[curDigIndex] = curPhoneKey[i];
printWordsUtil(number, curDigIndex+1, output);
if (number[curDigIndex] <= 1) // for 0 or 1
return;
}
}
public static void main(String[] args) {
int number[] = {2, 3, 4};
printPhoneWords(number);
System.out.println();
}
Oracle SQL: Usable with any phone number length and can easily support localization.
CREATE TABLE digit_character_map (digit number(1), character varchar2(1));
SELECT replace(permutations,' ','') AS permutations
FROM (SELECT sys_connect_by_path(map.CHARACTER,' ') AS permutations, LEVEL AS lvl
FROM digit_character_map map
START WITH map.digit = substr('12345',1,1)
CONNECT BY digit = substr('12345',LEVEL,1))
WHERE lvl = length('12345');
Here is one for pain C. This one is likley not efficet (in fact I don't think it is at all). But there are some intresting aspects to it.
Whats nice about this is that there is no real limit to the size of the string (no character limit) This allows you to generate longer and longer strings if need be just by waiting.
#include <stdlib.h>
#include <stdio.h>
#define CHARACTER_RANGE 95 // The range of valid password characters
#define CHARACTER_OFFSET 32 // The offset of the first valid character
void main(int argc, char *argv[], char *env[])
{
int i;
long int string;
long int worker;
char *guess; // Current Generation
guess = (char*)malloc(1); // Allocate it so free doesn't fail
int cur;
for ( string = 0; ; string++ )
{
worker = string;
free(guess);
guess = (char*)malloc((string/CHARACTER_RANGE+1)*sizeof(char)); // Alocate for the number of characters we will need
for ( i = 0; worker > 0 && i < string/CHARACTER_RANGE + 1; i++ ) // Work out the string
{
cur = worker % CHARACTER_RANGE; // Take off the last digit
worker = (worker - cur) / CHARACTER_RANGE; // Advance the digits
cur += CHARACTER_OFFSET;
guess[i] = cur;
}
guess[i+1] = '\0'; // NULL terminate our string
printf("%s\t%d\n", guess, string);
}
}
This problem is similar to this leetcode problem. Here is the answer I submitted for this problem to leetcode (check github and video for explanation).
So the very first thing we need is some way to hold the mappings of a digit and we can use a map for this:
private Map<Integer, String> getDigitMap() {
return Stream.of(
new AbstractMap.SimpleEntry<>(2, "abc"),
new AbstractMap.SimpleEntry<>(3, "def"),
new AbstractMap.SimpleEntry<>(4, "ghi"),
new AbstractMap.SimpleEntry<>(5, "jkl"),
new AbstractMap.SimpleEntry<>(6, "mno"),
new AbstractMap.SimpleEntry<>(7, "pqrs"),
new AbstractMap.SimpleEntry<>(8, "tuv"),
new AbstractMap.SimpleEntry<>(9, "wxyz"))
.collect(Collectors.toMap(AbstractMap.SimpleEntry::getKey,
AbstractMap.SimpleEntry::getValue));
}
The above method is preparing the map and next method I would use is to provide the mapping for provided digit:
private String getDigitMappings(String strDigit, Map<Integer,String> digitMap) {
int digit = Integer.valueOf(strDigit);
return digitMap.containsKey(digit) ? digitMap.get(digit) : "";
}
This problem can be solved using backtracking and a backtracking solution generally has a structure where the method signature will contain: result container, temp results, original source with index etc. So the method structure would be of the form:
private void compute(List<String> result, StringBuilder temp, String digits, int start, Map<Integer, String> digitMap) {
// Condition to populate temp value to result
// explore other arrangements based on the next input digit
// Loop around the mappings of a digit and then to explore invoke the same method recursively
// Also need to remove the digit which was in temp at last so as to get proper value in temp for next cycle in loop
}
And now the method body can be filled as (result will be kept in a list, temp in string builder etc.)
private void compute(List<String> result, StringBuilder temp, String digits, int start, Map<Integer, String> digitMap) {
if(start >= digits.length()) { // condition
result.add(temp.toString());
return;
}
String letters = getDigitMappings(digits.substring(start, start + 1), digitMap); // mappings of a digit to loop around
for (int i = 0; i < letters.length(); i++) {
temp.append(letters.charAt(i));
compute(result, temp, digits, start+1, digitMap); //explore for remaining digits
temp.deleteCharAt(temp.length() - 1); // remove last in temp
}
}
And finally the method can be invoked as:
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if(digits == null || digits.length() == 0) return result;
compute(result, new StringBuilder(), digits, 0, getDigitMap());
return result;
}
Now the max mapped chars for a digit can be 4 (e.g. 9 has wxyz) and backtracking involves exhaustive search to explore all possible arrangements (state space tree) so for a digit of size n we are going to have 4x4x4....n times i.e. complexity would be O(4^n).
This version in C# is reasonably efficient, and it works for non-western digits (like "???????" for example).
static void Main(string[] args)
{
string phoneNumber = null;
if (1 <= args.Length)
phoneNumber = args[0];
if (string.IsNullOrEmpty(phoneNumber))
{
Console.WriteLine("No phone number supplied.");
return;
}
else
{
Console.WriteLine("Alphabetic phone numbers for \"{0}\":", phoneNumber);
foreach (string phoneNumberText in GetPhoneNumberCombos(phoneNumber))
Console.Write("{0}\t", phoneNumberText);
}
}
public static IEnumerable<string> GetPhoneNumberCombos(string phoneNumber)
{
phoneNumber = RemoveNondigits(phoneNumber);
if (string.IsNullOrEmpty(phoneNumber))
return new List<string>();
char[] combo = new char[phoneNumber.Length];
return GetRemainingPhoneNumberCombos(phoneNumber, combo, 0);
}
private static string RemoveNondigits(string phoneNumber)
{
if (phoneNumber == null)
return null;
StringBuilder sb = new StringBuilder();
foreach (char nextChar in phoneNumber)
if (char.IsDigit(nextChar))
sb.Append(nextChar);
return sb.ToString();
}
private static IEnumerable<string> GetRemainingPhoneNumberCombos(string phoneNumber, char[] combo, int nextDigitIndex)
{
if (combo.Length - 1 == nextDigitIndex)
{
foreach (char nextLetter in phoneNumberAlphaMapping[(int)char.GetNumericValue(phoneNumber[nextDigitIndex])])
{
combo[nextDigitIndex] = nextLetter;
yield return new string(combo);
}
}
else
{
foreach (char nextLetter in phoneNumberAlphaMapping[(int)char.GetNumericValue(phoneNumber[nextDigitIndex])])
{
combo[nextDigitIndex] = nextLetter;
foreach (string result in GetRemainingPhoneNumberCombos(phoneNumber, combo, nextDigitIndex + 1))
yield return result;
}
}
}
private static char[][] phoneNumberAlphaMapping = new char[][]
{
new char[] { '0' },
new char[] { '1' },
new char[] { 'a', 'b', 'c' },
new char[] { 'd', 'e', 'f' },
new char[] { 'g', 'h', 'i' },
new char[] { 'j', 'k', 'l' },
new char[] { 'm', 'n', 'o' },
new char[] { 'p', 'q', 'r', 's' },
new char[] { 't', 'u', 'v' },
new char[] { 'w', 'x', 'y', 'z' }
};
I tried it in ruby, and came up with a different way of doing, it's probably not efficient, like time and space O(?) at this point, but I like it because it uses Ruby's builtin Array.product method. What do you think?
EDIT: I see a very similar solution in Python above, but I hadn't seen it when I added my answer
def phone_to_abc(phone)
phone_abc = [
'0', '1', 'abc', 'def', 'ghi',
'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'
]
phone_map = phone.chars.map { |x| phone_abc[x.to_i].chars }
result = phone_map[0]
for i in 1..phone_map.size-1
result = result.product(phone_map[i])
end
result.each { |x|
puts "#{x.join}"
}
end
phone_to_abc('86352')
#include <sstream>
#include <map>
#include <vector>
map< int, string> keyMap;
void MakeCombinations( string first, string joinThis , vector<string>& eachResult )
{
if( !first.size() )
return;
int length = joinThis.length();
vector<string> result;
while( length )
{
string each;
char firstCharacter = first.at(0);
each = firstCharacter;
each += joinThis[length -1];
length--;
result.push_back(each);
}
first = first.substr(1);
vector<string>::iterator begin = result.begin();
vector<string>::iterator end = result.end();
while( begin != end)
{
eachResult.push_back( *begin);
begin++;
}
return MakeCombinations( first, joinThis, eachResult);
}
void ProduceCombinations( int inNumber, vector<string>& result)
{
vector<string> inputUnits;
int number = inNumber;
while( number )
{
int lastdigit ;
lastdigit = number % 10;
number = number/10;
inputUnits.push_back( keyMap[lastdigit]);
}
if( inputUnits.size() == 2)
{
MakeCombinations(inputUnits[0], inputUnits[1], result);
}
else if ( inputUnits.size() > 2 )
{
MakeCombinations( inputUnits[0] , inputUnits[1], result);
vector<string>::iterator begin = inputUnits.begin();
vector<string>::iterator end = inputUnits.end();
begin += 2;
while( begin != end )
{
vector<string> intermediate = result;
vector<string>::iterator ibegin = intermediate.begin();
vector<string>::iterator iend = intermediate.end();
while( ibegin != iend)
{
MakeCombinations( *ibegin , *begin, result);
//resultbegin =
ibegin++;
}
begin++;
}
}
else
{
}
return;
}
int _tmain(int argc, _TCHAR* argv[])
{
keyMap[1] = "";
keyMap[2] = "abc";
keyMap[3] = "def";
keyMap[4] = "ghi";
keyMap[5] = "jkl";
keyMap[6] = "mno";
keyMap[7] = "pqrs";
keyMap[8] = "tuv";
keyMap[9] = "wxyz";
keyMap[0] = "";
string inputStr;
getline(cin, inputStr);
int number = 0;
int length = inputStr.length();
int tens = 1;
while( length )
{
number += tens*(inputStr[length -1] - '0');
length--;
tens *= 10;
}
vector<string> r;
ProduceCombinations(number, r);
cout << "[" ;
vector<string>::iterator begin = r.begin();
vector<string>::iterator end = r.end();
while ( begin != end)
{
cout << *begin << "," ;
begin++;
}
cout << "]" ;
return 0;
}
In Python, iterative:
digit_map = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz',
}
def word_numbers(input):
input = str(input)
ret = ['']
for char in input:
letters = digit_map.get(char, '')
ret = [prefix+letter for prefix in ret for letter in letters]
return ret
ret is a list of results so far; initially it is populated with one item, the empty string. Then, for each character in the input string, it looks up the list of letters that match it from the dict defined at the top. It then replaces the list ret with the every combination of existing prefix and possible letter.
You find source (Scala) here and an working applet here.
Since 0 and 1 aren't matched to characters, they build natural breakpoints in numbers. But they don't occur in every number (except 0 at the beginning). Longer numbers like +49567892345 from 9 digits starting, can lead to OutOfMemoryErrors. So it would be better to split a number into groups like
to see, if you can make sense from the shorter parts. I wrote such a program, and tested some numbers from my friends, but found rarely combinations of shorter words, which could be checked in a dictionary for matching, not to mention single, long words.
So my decision was to only support searching, no full automation, by displaying possible combinations, encouraging splitting the number by hand, maybe multiple time.
So I found +-RAD JUNG (+-bycicle boy).
If you accept misspellings, abbreviations, foreign words, numbers as words, numbers in words, and names, your chance to find a solution is much better, than without fiddling around.
246848 => 2hot4u (too hot for you)
466368 => goodn8 (good night)
1325 => 1FCK (Football club)
53517 => JDK17 (Java Developer Kit)
are things a human might observe - to make an algorithm find such things is rather hard.
I am rather a newbie so please correct me wherever I am wrong.
First thing is looking into space & time complexity. Which is really bad since it's factorial so for factorial(7) = 5040 any recursive algorithm would do. But for factorial(12) ~= 4 * 10^8 which can cause stack overflow in recursive solution.
So I would not attempt a recursive algorithm. Looping solution is very straight forward using "Next Permutation".
So I would create and array {0, 1, 2, 3, 4, 5} and generate all permutation and while printing replace them with respective characters eg. 0=A, 5=F
Next Perm algorithm works as follows. eg Given 1,3,5,4 next permutation is 1,4,3,5
Steps for finding next perm.
From right to left, find first decreasing number. eg 3
From left to right, find lowest number bigger than 3 eg. 4
Swap these numbers as reverse the subset. 1,4,5,3 reverse subset 1,4,3,5
Using Next permutation ( or rotation) you generate specific subset of permutations, say you want to show 1000 permutations starting from a particular phone number. This can save you from having all numbers in memory. If I store numbers as 4 byte integers, 10^9 bytes = 1 GB !.
In C++(recursive):
string pattern[] = {"0",".,!","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"};
ofstream keyout("keypad.txt");
void print_keypad(char* str, int k, vector<char> patt, int i){
if(str[k] != '\0')
{
int x = str[k] - '0';
for(int l = 0; l < pattern[x].length(); l++)
{
patt[i] = pattern[x][l];
print_keypad(str, k+1, patt, i+1);
}
keyout << endl;
}
else if(i == k)
{
string st(patt.data());
keyout << st << endl;
return;
}
}
This function can be called with 'k' and 'i' equal to zero.
Anyone, who requires more illustration to understand the logic, can combine recursion technique with following output:
ADG
ADH
ADI
AEG
AEH
AEI
AFG
AFH
AFI
BDG
BDH
BDI
BEG
BEH
BEI
BFG
BFH
...
namespace WordsFromPhoneNumber
{
/// <summary>
/// Summary description for WordsFromPhoneNumber
/// </summary>
[TestClass]
public class WordsFromPhoneNumber
{
private static string[] Chars = { "0", "1", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ" };
public WordsFromPhoneNumber()
{
//
// TODO: Add constructor logic here
//
}
#region overhead
private TestContext testContextInstance;
/// <summary>
///Gets or sets the test context which provides
///information about and functionality for the current test run.
///</summary>
public TestContext TestContext
{
get
{
return testContextInstance;
}
set
{
testContextInstance = value;
}
}
#region Additional test attributes
//
// You can use the following additional attributes as you write your tests:
//
// Use ClassInitialize to run code before running the first test in the class
// [ClassInitialize()]
// public static void MyClassInitialize(TestContext testContext) { }
//
// Use ClassCleanup to run code after all tests in a class have run
// [ClassCleanup()]
// public static void MyClassCleanup() { }
//
// Use TestInitialize to run code before running each test
// [TestInitialize()]
// public void MyTestInitialize() { }
//
// Use TestCleanup to run code after each test has run
// [TestCleanup()]
// public void MyTestCleanup() { }
//
#endregion
[TestMethod]
public void TestMethod1()
{
IList<string> words = Words(new int[] { 2 });
Assert.IsNotNull(words, "null");
Assert.IsTrue(words.Count == 3, "count");
Assert.IsTrue(words[0] == "A", "a");
Assert.IsTrue(words[1] == "B", "b");
Assert.IsTrue(words[2] == "C", "c");
}
[TestMethod]
public void TestMethod23()
{
IList<string> words = Words(new int[] { 2 , 3});
Assert.IsNotNull(words, "null");
Assert.AreEqual(words.Count , 9, "count");
Assert.AreEqual(words[0] , "AD", "AD");
Assert.AreEqual(words[1] , "AE", "AE");
Assert.AreEqual(words[2] , "AF", "AF");
Assert.AreEqual(words[3] , "BD", "BD");
Assert.AreEqual(words[4] , "BE", "BE");
Assert.AreEqual(words[5] , "BF", "BF");
Assert.AreEqual(words[6] , "CD", "CD");
Assert.AreEqual(words[7] , "CE", "CE");
Assert.AreEqual(words[8] , "CF", "CF");
}
[TestMethod]
public void TestAll()
{
int[] number = new int [4];
Generate(number, 0);
}
private void Generate(int[] number, int index)
{
for (int x = 0; x <= 9; x += 3)
{
number[index] = x;
if (index == number.Length - 1)
{
var w = Words(number);
Assert.IsNotNull(w);
foreach (var xx in number)
{
Console.Write(xx.ToString());
}
Console.WriteLine(" possible words:\n");
foreach (var ww in w)
{
Console.Write("{0} ", ww);
}
Console.WriteLine("\n\n\n");
}
else
{
Generate(number, index + 1);
}
}
}
#endregion
private IList<string> Words(int[] number)
{
List<string> words = new List<string>(100);
Assert.IsNotNull(number, "null");
Assert.IsTrue(number.Length > 0, "length");
StringBuilder word = new StringBuilder(number.Length);
AddWords(number, 0, word, words);
return words;
}
private void AddWords(int[] number, int index, StringBuilder word, List<string> words)
{
Assert.IsTrue(index < number.Length, "index < length");
Assert.IsTrue(number[index] >= 0, "number >= 0");
Assert.IsTrue(number[index] <= 9, "number <= 9");
foreach (var c in Chars[number[index]].ToCharArray())
{
word.Append(c);
if (index < number.Length - 1)
{
AddWords(number, index + 1, word, words);
}
else
{
words.Add(word.ToString());
}
word.Length = word.Length - 1;
}
}
}
}
Source: Stackoverflow.com