# Month: November 2014

Problem: Given a sequence of numbers, show all possible letter combinations in a telephone keypad.

Recursive solution in Python:

```keyboard = {
'1': [],
'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'],
'0': []
}

def printkeys(numbers, prefix=""):
if len(numbers)==0:
print prefix
return

for letter in keyboard[numbers[0]]:
printkeys(numbers[1:], prefix+letter)

printkeys("234")
```

Output:

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

In case you can’t use Python’s itertools or in case you want a simple, recursive python implementation for a permutation of a list:

```def perm(a,k=0):
if(k==len(a)):
print a
else:
for i in xrange(k,len(a)):
a[k],a[i] = a[i],a[k]
perm(a, k+1)
a[k],a[i] = a[i],a[k]

perm([1,2,3])
```

Output:

```[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]
```

This Python implementation is based in the algorithm presented in the book Computer Algorithms by Horowitz, Sahni and Rajasekaran.