-1

I have to generate all the possible combinations of letters that represents a number sequence in a telephone... for example: if the entry is '423', the output should be:

GAD   GAE   GAF   GBD   GBE   GBF   GCD   GCE   GCF    
HAD   HAE   HAF   HBD   HBE   HBF   HCD   HCE   HCF   
IAD   IAE   IAF   IBD   IBE   IBF   ICD   ICE   ICF

I must use recursion to solve this... I started using a dictionary like this:

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

But I don't know how can I use a recursion here... Could someone help?

I thought something like this to start with:

def telephoneSequence(str):
    for i in range (len(str)):
        return dic[str[i]]
4
  • 1
    Start with generating entries of length 1. Than ask yourself how can an entry of length 1 be turned to a legal entry of length 2. Feb 18, 2013 at 13:26
  • 9
    Welcome to Stack Overflow! It looks like you want us to write some code for you. While many users are willing to produce code for a coder in distress, they usually only help when the poster has already tried to solve the problem on their own. A good way to demonstrate this effort is to include the code you've written so far, example input (if there is any), the expected output, and the output you actually get (console output, stack traces, compiler errors - whatever is applicable). The more detail you provide, the more answers you are likely to receive.
    – Martijn Pieters
    Feb 18, 2013 at 13:27
  • 1
    @user2083363, don't post code in comments. Edit your question and add the code to it. Feb 18, 2013 at 13:30
  • One general approach is: to generate all the outputs for the number 423 (e.g.: letters(number='423'), you need to go through all the possible letters for 4 (for char in dic[4]:), and for each of these letters append all the outputs for the number 23 (letters(number='23')) As you can see, a part of the solution description ("all the outputs for the number…") reads the same as the whole problem, that's where you recurse. (Until you no longer need to generate the "tail" of the number because the number only has one digit.)
    – millimoose
    Feb 18, 2013 at 13:34

3 Answers 3

10

I think you're looking for itertools.product:

>>> import itertools
>>> list(itertools.product('GHI','ABC','DEF'))
[('G', 'A', 'D'), ('G', 'A', 'E'), ('G', 'A', 'F'), ('G', 'B', 'D'), ('G', 'B', 'E'), ('G', 'B', 'F'), ('G', 'C', 'D'), ('G', 'C', 'E'), ('G', 'C', 'F'), ('H', 'A', 'D'), ('H', 'A', 'E'), ('H', 'A', 'F'), ('H', 'B', 'D'), ('H', 'B', 'E'), ('H', 'B', 'F'), ('H', 'C', 'D'), ('H', 'C', 'E'), ('H', 'C', 'F'), ('I', 'A', 'D'), ('I', 'A', 'E'), ('I', 'A', 'F'), ('I', 'B', 'D'), ('I', 'B', 'E'), ('I', 'B', 'F'), ('I', 'C', 'D'), ('I', 'C', 'E'), ('I', 'C', 'F')]

This gives you a bunch of tuples, but you can ''.join them easily.

>>> list(''.join(p) for p in itertools.product('GHI','ABC','DEF'))
['GAD', 'GAE', 'GAF', 'GBD', 'GBE', 'GBF', 'GCD', 'GCE', 'GCF', 'HAD', 'HAE', 'HAF', 'HBD', 'HBE', 'HBF', 'HCD', 'HCE', 'HCF', 'IAD', 'IAE', 'IAF', 'IBD', 'IBE', 'IBF', 'ICD', 'ICE', 'ICF']

Of course, this isn't recursive and won't help you out if you have other constraining forces (a professor perhaps?). I leave this answer to demonstrate how powerful the python standard library is and to show that recursion really isn't the best tool for this sort of problem (at least not in python).

6
  • That would be the sensitive solution, but OP says he must use recursion...
    – tobias_k
    Feb 18, 2013 at 13:34
  • Oh, right. I missed the recursive part ... Well, maybe this will be useful for someone without that restriction.
    – mgilson
    Feb 18, 2013 at 13:35
  • or to check his result is correct.
    – MatthieuW
    Feb 18, 2013 at 15:27
  • You haven't answered the OP's question.
    – martineau
    Feb 18, 2013 at 15:49
  • @martineau -- I think a "don't do it that way" is a reasonable answer to a question ... Recursion in python has lots of issues and this is nothing more than a nested loop. itertools.product is the tool that should be used to solve this problem in any production code which is why I leave it as an answer in hopes that future visitors don't stumble across this and think that recursion is the right way to do this (even if it is what OP asked for).
    – mgilson
    Feb 18, 2013 at 15:53
4

If you do not want to use itertools.product and implement it recursively, you can do something like:

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

def permutatePhoneNum(number):
    result = []
    if len(number) == 1:
        return [i for i in d[number]]
    restPerm = permutatePhoneNum(number[1:])
    for chr in d[number[0]]:
        for rest in restPerm:
            result.append(chr + rest)
    return result

Then, you can use it as following:

>>> permutatePhoneNum("423")
['GAD', 'GAE', 'GAF', 'GBD', 'GBE', 'GBF', 'GCD', 'GCE', 'GCF', 'HAD', 'HAE', 
'HAF', 'HBD', 'HBE', 'HBF', 'HCD', 'HCE', 'HCF', 'IAD', 'IAE', 'IAF', 'IBD', 
'IBE', 'IBF', 'ICD', 'ICE', 'ICF']
0

Doing being limited to only using recursion was trickier to get right than I expected -- being somewhat out of practice since Python has several useful built-ins that make doing such things fairly easy. But, FWIW, here it is:

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

def teleseq(digits, letters=[], result=None):
    if result is None: result = []
    if len(digits) == 1:
        result.extend(''.join(letters+[letter]) for letter in KEYPAD[digits[0]])
    else:
        for letter in KEYPAD[digits[0]]:
            teleseq(digits[1:], letters+[letter], result)
    return result

print sorted(teleseq('432'))

Output:

['GDA', 'GDB', 'GDC', 'GEA', 'GEB', 'GEC', 'GFA', 'GFB', 'GFC', 'HDA', 'HDB',
 'HDC', 'HEA', 'HEB', 'HEC', 'HFA', 'HFB', 'HFC', 'IDA', 'IDB', 'IDC', 'IEA',
 'IEB', 'IEC', 'IFA', 'IFB', 'IFC']

Not the answer you're looking for? Browse other questions tagged or ask your own question.