Permutations for digits represented by Phone Number

I have an interview in 2 days and I am having a very hard time finding a solutions for this question: What I want to do is .. for any phone number .. the program should print out all the possible strings it represents. For eg.) A 2 in the number can be replaced by 'a' or 'b' or 'c', 3 by 'd' 'e' 'f' etc. In this way how many possible permutations can be formed from a given phone number开发者_如何学运维. I don't want anyone to write code for it ... a good algorithm or psuedocode would be great.

Thank you

This is the popular correspondence table:

d = { '2': "ABC",
'3': "DEF",
'4': "GHI",
'5': "JKL",
'6': "MNO",
'7': "PQRS",
'8': "TUV",
'9': "WXYZ",
}

Given this, or any other d, (executable) pseudocode to transform a string of digits into all possible strings of letters:

def digstolets(digs):
  if len(digs) == 0:
    yield ''
    return
  first, rest = digs[0], digs[1:]
  if first not in d:
    for x in digstolets(rest): yield first + x
    return
  else:
    for x in d[first]:
      for y in digstolets(rest): yield x + y

tweakable depending on what you want to do for characters in the input string that aren't between 2 and 9 included (this version just echoes them out!-).

For example,

print list(digstolets('1234'))

in this version emits

['1ADG', '1ADH', '1ADI', '1AEG', '1AEH', '1AEI', '1AFG', '1AFH', '1AFI', 
 '1BDG', '1BDH', '1BDI', '1BEG', '1BEH', '1BEI', '1BFG', '1BFH', '1BFI',
 '1CDG', '1CDH', '1CDI', '1CEG', '1CEH', '1CEI', '1CFG', '1CFH', '1CFI']

Edit: the OP asks for more explanation, here's an attempt. Function digstolets (digits to letters) takes a string of digits digs and yields a sequence of strings of characters which can be letters or "non-digits". 0 and 1 count as non-digits here because they don't expand into letters, just like spaces and punctuations don't -- only digits 2 to 9 included expand to letters (three possibilities each in most cases, four in two cases, since 7 can expand to any of PQRS and 9 can expand to any of WXYZ).

First, the base case: if nothing is left (string digs is empty), the only possible result is the empty string, and that's all, this recursive call is done, finished, kaput.

If digs is non-empty it can be split into a "head", the first character, and a "tail", all the rest (0 or more characters after the first one).

The "head" either stays as it is in the output, if a non-digit; or expands to any of three or four possibilities, if a digit. In either case, the one, three, or four possible expansions of the head must be concatenated with every possible expansion of the tail -- whence, the recursive call, to get all possible expansions of the tail (so we loop over all said possible expansion of the tail, and yield each of the one, three, or four possible expansions of the head concatenated with each possible expansion of the tail). And then, once again, th-th-that's all, folks.

I don't know how to put this in terms that are any more elementary -- if the OP is still lost after THIS, I can only recommend a serious, total review of everything concerning recursion. Removing the recursion in favor of an explicitly maintained stack cannot simplify this conceptual exposition -- depending on the language involved (it would be nice to hear about what languages the OP is totally comfortable with!), recursion elimination can be an important optimization, but it's never a conceptual simplification...!-)

If asked this in an interview, I'd start by breaking the problem down. What are the problems you have to solve?

First, you need to map a number to a set of letters. Some numbers will map to different numbers of letters. So start by figuring out how to store that data. Basically you want a map of a number to a collection of letters.

Once you're there, make it easier, how would you generate all the "words" for a 1-digit number? Basically how to iterate through the collection that's mapped to a given number. And how many possibilities are there?

OK, now the next step is, you've got two numbers and want to generate all the words. How would you do this if you were just gonna do it manually? You'd start with the first letter for the first number, and the first letter for the second number. Then go to the next letter for the second number, keeping the first letter for the first, etc. Think about it as numbers (basically indices into the collections for two numbers which each map to 3 letters):

00,01,02,10,11,12,20,21,22

So how would you generate that sequence of numbers in code?

Once you can do that, translating it to code should be trivial.

Good luck!

Another version in Java.

First it selects character arrays based on each digit of the phone number. Then using recursion it generates all possible permutations.

public class PhonePermutations {
    public static void main(String[] args) {
        char[][] letters = 
            {{'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'}};
        String n = "1234";
        char[][] sel = new char[n.length()][];
        for (int i = 0; i < n.length(); i++) {
            int digit = Integer.parseInt("" +n.charAt(i));
            sel[i] = letters[digit];
        }
        permutations(sel, 0, "");
    }

    public static void permutations(char[][] symbols, int n,  String s) {
        if (n == symbols.length) {
            System.out.println(s);
            return;
        }
        for (int i = 0; i < symbols[n].length; i ++) {
            permutations(symbols, n+1, s + symbols[n][i]);
        }
    }
}

This is a counting problem, so it usually helps to find a solution for a smaller problem, then think about how it expands to your general case.

If you had a 1 digit phone number, how many possibilities would there be? What if you had 2 digits? How did you move from one to the other, and could you come up with a way to solve it for n digits?

Here's what I came up with:

import java.util.*;

public class PhoneMmemonics {

    /**
     * Mapping between a digit and the characters it represents
     */
    private static Map<Character,List<Character>> numberToCharacters = new HashMap<Character,List<Character>>();

    static {
        numberToCharacters.put('0',new ArrayList<Character>(Arrays.asList('0')));
        numberToCharacters.put('1',new ArrayList<Character>(Arrays.asList('1')));
        numberToCharacters.put('2',new ArrayList<Character>(Arrays.asList('A','B','C')));
        numberToCharacters.put('3',new ArrayList<Character>(Arrays.asList('D','E','F')));
        numberToCharacters.put('4',new ArrayList<Character>(Arrays.asList('G','H','I')));
        numberToCharacters.put('5',new ArrayList<Character>(Arrays.asList('J','K','L')));
        numberToCharacters.put('6',new ArrayList<Character>(Arrays.asList('M','N','O')));
        numberToCharacters.put('7',new ArrayList<Character>(Arrays.asList('P','Q','R')));
        numberToCharacters.put('8',new ArrayList<Character>(Arrays.asList('T','U','V')));
        numberToCharacters.put('9',new ArrayList<Character>(Arrays.asList('W','X','Y','Z')));
    }

    /**
     * Generates a list of all the mmemonics that can exists for the number
     * @param phoneNumber
     * @return
     */
    public static List<String> getMmemonics(int phoneNumber) {

        // prepare results
        StringBuilder stringBuffer = new StringBuilder();
        List<String> results = new ArrayList<String>();

        // generate all the mmenonics
        generateMmemonics(Integer.toString(phoneNumber), stringBuffer, results);

        // return results
        return results;
    }

    /**
     * Recursive helper method to generate all mmemonics
     * 
     * @param partialPhoneNumber Numbers in the phone number that haven't converted to characters yet
     * @param partialMmemonic The partial word that we have come up with so far
     * @param results total list of all results of complete mmemonics
     */
    private static void generateMmemonics(String partialPhoneNumber, StringBuilder partialMmemonic, List<String> results) {

        // are we there yet?
        if (partialPhoneNumber.length() == 0) {

                   //Printing the pnemmonics
                   //System.out.println(partialMmemonic.toString());

            // base case: so add the mmemonic is complete
            results.add(partialMmemonic.toString());
            return;
        }

        // prepare variables for recursion
        int currentPartialLength = partialMmemonic.length();
        char firstNumber = partialPhoneNumber.charAt(0);
        String remainingNumbers = partialPhoneNumber.substring(1);

        // for each character that the single number represents
        for(Character singleCharacter : numberToCharacters.get(firstNumber)) {

            // append single character to our partial mmemonic so far
            // and recurse down with the remaining characters
            partialMmemonic.setLength(currentPartialLength);
            generateMmemonics(remainingNumbers, partialMmemonic.append(singleCharacter), results);
        }
    }
}

Use recursion and a good data structure to hold the possible characters. Since we are talking numbers, an array of array would work.

char[][] toChar = {{'0'}, {'1'}, {'2', 'A', 'B', 'C'}, ..., {'9', 'W', 'X'. 'Y'} };

Notice that the ith array in this array of arrays holds the characters corresponding to the ith button on the telephone. I.e., tochar[2][0] is '2', tochar[2][1] is 'A', etc.

The recursive function will take index as a parameter. It will have a for loop that iterates through the replacement chars, replacing the char at that index with one from the array. If the length equals the length of the input string, then it outputs the string.

In Java or C#, you would want to use a string buffer to hold the changing string.

function recur(index)
    if (index == input.length) output stringbuffer
    else
        for (i = 0; i < tochar[input[index]].length; i++)
             stringbuffer[index] = tochar[input[index]][i]
             recur(index + 1)

A question that comes to my mind is the question of what should 0 and 1 become in such a system? Otherwise, what you have is something where you could basically just recursively go through the letters for each value in the 2-9 range for the simple brute force way to churn out all the values.

Assuming normal phone number length within North America and ignoring special area codes initially there is also the question of how many digits represent 4 values instead of 3 as 7 and 9 tend to get those often unused letters Q and Z, because the count could range from 3^10 = 59,049 to 4^10 = 1,048,576. The latter is 1024 squared, I just noticed.

The OP seems to be asking for an implementation as he is struggling to understand the pseudocode above. Perhaps this Tcl script will help:

array set d {
    2 {a b c}
    3 {d e f} 
    4 {g h i}
    5 {j k l}
    6 {m n o}
    7 {p q r s}
    8 {t u v}
    9 {w x y z}
}

proc digstolets {digits} {
    global d

    set l [list]
    if {[string length $digits] == 0} {
        return $l
    }

    set first [string index $digits 0]
    catch {set first $d($first)}

    if {[string length $digits] == 1} {
        return $first
    }

    set res [digstolets [string range $digits 1 end]]
    foreach x $first {
        foreach y $res {
            lappend l $x$y
        }
    }

    return $l
}

puts [digstolets "1234"]

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

    vector<string> finalres;

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

C program:

char *str[] = {"0", "1", "2abc", "3def", "4ghi", "5jkl", "6mno", "7pqrs", "8tuv", "9wxyz"};

const char number[]="2061234569";

char printstr[15];

int len;

printph(int index)
{

     int i;
     int n;
     if (index == len)
     {
        printf("\n");
        printstr[len] = '\0';
        printf("%s\n", printstr);
        return;
     }

     n =number[index] - '0';
     for(i = 0; i < strlen(str[n]); i++)
     {
        printstr[index] = str[n][i];
        printph(index +1);
     }
}

Call

  printph(0);