Anagramas con Python

En el post anterior comentaba como me pongo a ratos con el libro Python for Software Design, versión impresa del conocido How to Think Like a Computer Scientist. Como ya indiqué, se trata de una fantástica introducción al lenguaje Python del profesor Allen B. Downey.

En el ejercicio 4 del capítulo 12 propone un ejercicio para explorar un diccionario en busca de anagramas. Leemos en la Wikipedia que un anagrama es una palabra o frase que resulta de la transposición de letras de otra palabra o frase. Por ejemplo roma, amor, omar y mora son anagramas, así como lámina y animal.

El objetivo de la práctica es escribir una serie de funciones que impriman todos los conjuntos de anagramas del fichero (en nuestro caso un diccionario español, que podemos obtener en este enlace). Estas son las mías

from string import join,maketrans

def encuentraAnagramas():
  anagramas={}
  fin = open("E:\\ES.txt")
  intab = "áéíóú"
  outtab = "aeiou"
  trantab = maketrans(intab, outtab)
  for line in fin:
     word  = line.strip()
     word2 = word.translate(trantab)
     l=list(word2)
     l.sort()
     clave=join(l,'')
     try:
         anagramas[clave].append(word)
     except KeyError:
         anagramas[clave]=[word]
  return anagramas

def buscador(palabra,diccionario):
   lpalabra=list(palabra)
   lpalabra.sort()
   clave=join(lpalabra,'')
   return(diccionario[clave])


>>> f=encuentraAnagramas()
>>> buscador('monja',f)
['jamón', 'mojan', 'monja']
>>> buscador('roma',f)
['amor', 'armo', 'armó', 'mora', 'ramo', 'roma']
>>> buscador('estados',f)
['dotases', 'estados']
>>> buscador('rebuscado',f)
['becuadros', 'rebuscado']

¿Cómo funciona esto? El truco, si es que hay alguno, consiste en usar una de las estructuras de datos más potentes de Python, los diccionarios, para recorrer la lista de palabras e ir formando un diccionario (lo que se denomina un hash en Perl o array asociativo en PHP) que conecte una clave con la lista de todas las palabras que sean anagramas entre sí. Pero, ¿cómo podemos organizar 'becuadros' y 'rebuscado' para que nos de una clave única de búsqueda? La respuesta la encontré hace tiempo leyendo un artículo de A.K.Dewdney en su estupenda columna 'Computer Recreations' de 'Scientific American' ('Investigación y Ciencia'): ordenar las letras de las palabras alfabéticamente. Veamos como funciona:

>>> p='retarais'
>>> l=list(p)
>>> l
['r', 'e', 't', 'a', 'r', 'a', 'i', 's']
>>> l.sort()
>>> l
['a', 'a', 'e', 'i', 'r', 'r', 's', 't']
>>> f['aaeirrst']
['arterias', 'arter\xedas', 'estirara', 'estirar\xe1', 'estriara', 'estriar\xe1', 'iterar\xe1s', 'rater\xedas', 'restar\xeda', 'retarais', 'retar\xedas', 'traer\xedas']
>>> for item in _:
print item,
arterias arterías estirara estirará estriara estriará iterarás raterías restaría retarais retarías traerías

Todas estas palabras, cuando sus letras son ordenadas alfabéticamente, convergen en 'aaeirrst'. Esa es la clave de búsqueda para los anagramas que podemos formar con estas letras. Con todas las piezas juntas, no es difícil encontrar cuales son las listas más grandes de anagramas... para lo que usaremos otro diccionario:

d={}
for i in f.keys():
  cantidad=len(f[i])
      try:
          d[cantidad].append(f[i])
      except KeyError:
          d[cantidad]=[f[i]]
for i in d.keys()[-4:]:
  print 'De longitud ',i
  for lista in d[i]:
      print '(',
      for elem in lista:
          print elem,
      print ')',
  print

Y estas son las listas de anagramas resultantes:

De longitud 11
( arresta arteras rastrea rateras restara restará retaras retarás retrasa traerás trasera ) ( artesonar atraernos atronarse nortearas nortearás ratearnos ratoneras sortearan sortearán tornearas tornearás ) ( alertos estarlo loteras orlaste relatos resalto resaltó soltaré soltera toleras tráelos ) ( entro entró norte rento rentó roten tenor terno torne torné treno ) ( espora operas opresa posaré repaso repasó reposa separo separó áspero óperas ) ( apretar pararte partear partera reparta reptara reptará trapear trapera trepara trepará ) ( entréis estiren estríen inertes inserte inserté interés rentéis rientes sentiré tírense ) ( cansaré cenaras cenarás cesaran cesarán encaras ensacar nacerás nácares secaran secarán ) ( enteros ernesto estreno estrenó eternos noreste nortees sorteen teneros tenores tornees ) ( caernos caserón cesaron coserán cráneos córneas encaros enrosca escoran roncase secaron ) ( amiste emitas estima matéis mesita metáis metías semita temáis temías timase ) ( ensarte ensarté enteras entesar entrase esteran estrena eternas rentase retasen sentaré )

De longitud 12
( canteros cantores cartones constaré contarse conteras contraes cornetas cortasen encastró roncaste troncase ) ( acaréis aceráis acerías caerías careáis casería cesaría escaria reacias recaías saciaré secaría ) ( alcores caerlos caleros calores colarse corales coserla créalos cóleras escolar laceros secarlo ) ( arreste arresté erraste esterar rastree rastreé restaré retarse retrase retrasé traerse térreas ) ( ardemos dameros daremos demoras desamor desarmo desarmó domarse maderos medrosa moderas redomas ) ( arrestan ensartar entraras entrarás narraste rastrean rentaras rentarás restaran restarán retrasan transaré ) ( abatirse abiertas baterías batieras estibara estibará estiraba estriaba rabietas rebatáis rebatías retabais ) ( acares aceras caerás careas casaré casera cesara cesará resaca sacaré secara secará ) ( asentir entráis estiran estrían inserta instaré rentáis retinas sentirá tiernas tirasen triasen ) ( entrarais entrarías estiraran estirarán estriaran estriarán insertara insertará rentarais rentarías restarían ternarias ) ( arterias arterías estirara estirará estriara estriará iterarás raterías restaría retarais retarías traerías )

De longitud 14
( artesón ensarto ensartó norteas notarse ratones rentosa rotasen sonarte sortean tornase torneas toserán tráenos )

De longitud 16
( arresto arrestó arteros ostrera rastreo rastreó rateros retraso retrasó rotarse sortear terrosa toreras torrase traeros trasero ) ( albores balsero besarlo boleras labores rebalso rebalsó resbalo resbaló roblase róbales róbelas saberlo salobre ábrelos árboles )







Alguien muy cercano y muy querido me dijo que estos post le resultaban inspiradores y le recordaban a los ejercicios de estilo Raymond Queneau (fundador de Oulipo), así que si no has entendido nada de todo esto espero que al menos disfrutes con el resultado ;-) Como siempre, gracias por venir. Si te gustó el post puedes apuntarte a través del correo electrónico o por medio del feed RSS (más información acerca del RSS). También puedes seguirme a través de mis elementos compartidos, y a partir de ahora desde Twitter o Friendfeed.