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.

view sourceprint?

1.def ana(s,file_in):

2. anas=anagrams(s)

3. lst_ana=del_duplicates(anas)

4. resultado=filtro(file_in,lst_ana)

5. 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:

view sourceprint?

1.def filtro(file_in,lst_ana):

2. """One word in each line."""

3. fin=open(file_in)

4. lst_pal=[pal.strip() for pal in fin.read().split('\n')]

5. lst_ana_final= [pal for pal in lst_pal if pal in lst_ana]

6. fin.close()

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

view sourceprint?

1.def del_duplicates(lst):

2. if len(lst) == 0:

3.  return lst

4. elif lst.count(lst[0]) > 1:

5.  return del_duplicates(lst[1:])

6. else:

7.  return [lst[0]] + del_duplicates(lst[1:])

8.  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!

view sourceprint?

01.def anagrams(s):

02. # Return the list of anagrams for s

03. if s == "":

04.  return [s]

05. else:

06.  ans = []

07.  for w in anagrams(s[1:]):

08.   for pos in range(len(w)+1):

09.    ans.append(w[:pos]+s[0]+w[pos:])

10.  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!!