Anagramas

Em post anterior falámos de Will McGunan e dos problemas que colocam quando está a seleccionar candidatos para um emprego onde é preciso saber Python. A segunda questão que coloca é um pouco mais complexa. Temos uma palavra e uma lista de palavras guardadas num ficheiro, uma por linha. A ideia é construir todos os anagramas da palavra dada que são palavras da lista.

Por exemplo, roma é um anagrama de amor.


Vamos construir a solução por etapas.

def ana(s,file_in): 
 anas=anagrams(s)
 lst_ana=del_duplicates(anas)
 resultado=filtro(file_in,lst_ana)
 return resultado

Este é o nosso programa principal! Usa três programas auxiliares:

anagrams: para calcular a lista de anagramas de uma palavra

del_duplicates: que elimina eventuais duplicações

filtro: que selecciona quais os anagramas que são palavras válidas.

Analisemos os casos mais simples, começando pelo processo de filtragem:

def filtro(file_in,lst_ana):
 """One word in each line."""
 fin=open(file_in)
 lst_pal=[pal.strip() for pal in fin.read().split('\n')]
 lst_ana_final= [pal for pal in lst_pal if pal in lst_ana]
 fin.close()
 return lst_ana_final

Lemos o ficheiro todo de uma só vez, dividimos em palavras e retiramos eventuais espaços em branco (linha 4). Na linha 5, apenas consideramos as palavras que estão quer na lista dos anagramas quer na lista das palavras. É agora a vez de eliminar as duplicações:

def del_duplicates(lst):
 if len(lst) == 0:
  return lst
 elif lst.count(lst[0]) > 1:
  return del_duplicates(lst[1:])
 else:
  return [lst[0]] + del_duplicates(lst[1:])
  return [lst[0]] + del_duplicates(lst[1:])

Trata-se de uma solução recursiva: a função chama-se a ela própria. Não era necessário usar recursividade, podendo, caso queira pensar numa solução mais convencional.

Deixámos para o fim a questão de encontrar os anagramas. E aqui, mais uma vez, a solução é recursiva. No entanto, agora não é fácil encontrar uma solução que não faça usa de recursividade. Experimente por si!

def anagrams(s):
 # Return the list of anagrams for s
 if s == "":
  return [s]
 else:
  ans = []
  for w in anagrams(s[1:]):
   for pos in range(len(w)+1):
    ans.append(w[:pos]+s[0]+w[pos:])
  return ans

Porque, e como, funciona esta solução? A ideia é a seguinte: fabricamos (recursivamente) os anagramas com a palavra sem o seu primeiro caracter, para depois inserirmos esse caracter em todas as posições possíveis em cada um dos anagramas gerados. O processo termina se a palavra não tiver nenhum caracter.

E pronto. Só falta testar. Arranje um ficheiro com palavras e faça o exercício. Acho que, desta vez, era capaz de conseguir o lugar!!