Telephone keypad combinations

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

permutations implemented in Python

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.

“A poesia está guardada nas palavras – é tudo que eu sei.
Meu fado é o de não saber quase tudo.
Sobre o nada eu tenho profundidades.
Não tenho conexões com a realidade.
Poderoso para mim não é aquele que descobre ouro.
Para mim poderoso é aquele que descobre as insignificâncias (do mundo e as nossas).
Por essa pequena sentença me elogiaram de imbecil.
Fiquei emocionado e chorei.
Sou fraco para elogios.”

Tratado geral das grandezas do ínfimo, Manoel de Barros

“The obsolescence of an implementation must be measured against other existing implementations, not against unrealized concepts.” The Mythical Man-month – Essays on Software Engineering. Freederick P. Brooks, Jr.