Encontrar Anagramas con Python

26/06/2017 | Autor: Eduardo Enriquez

Encontrar anagramas con Python

Hay ejercicios que aparecen una y otra vez a la hora de hacer entrevistas de trabajo. Y el ejercicio de encontrar los anagramas es uno de esos. 

Un anagrama es una palabra que se lee de adelante para atrás y atrás para adelante con sentido. O que mezclando sus letras encontramos nuevas palabras.  Ejemplos:

Alegan – Ángela Riesgo – Sergio
Desamparador – desparramado Licúa – Lucía
Conservadora – conversadora Amor – Roma

Más formalmente, un anagrama es una palabra o frase que resulta de la transposición de letras de otra palabra o frase (Anagrama según wikipedia). Esto es dos palabras que usan las mismas letras pero en distinto orden.

Y dió la casualidad que vi en un tweet la siguiente imágen que decia que utilizando el teorema fundamental de la aritmética se podía saber si dos palabras eran anagramas (@fermatslibrary).

Así que lo intenté hacer. Y lo primero que hay que hacer es conseguir 26 números primos (veasé mi post anterior obtener-numeros-primos-con-python) así podemos vincular cada letra ascii con un numero primo.

Así que repitiendo un poco el código de otro post:

import math
import string


def primeSieve(sieveSize):
    # Returns a list of prime numbers calculated using
    # the Sieve of Eratosthenes algorithm.
    sieve = [True] * sieveSize
    sieve[0] = False  # zero and one are not prime numbers
    sieve[1] = False
    # create the sieve
    for i in range(2, int(math.sqrt(sieveSize)) + 1):
        pointer = i * 2
        while pointer < sieveSize:
            sieve[pointer] = False
            pointer += i
        # compile the list of primes
        primes = []
        for i in range(sieveSize):
            if sieve[i] is True:
                primes.append(i)
    return primes


all_ascii = string.ascii_lowercase
primes = primeSieve(102)

ascii_primes = dict(zip(all_ascii, primes))

Al final podemos ver como usamos la libreria built-in de python string (python.org - string) para obtener todos los caracteres "abcdefghijklmnopqrstuvwxyz". Después con los números primos y las letras armamos un dict con zip(). Para qué, para que me quede un dictionary de la siguiente forma:

{
	'o': 47,
	'y': 97,
	'n': 43,
	'r': 61,
	'i': 23,
	'g': 17,
	'j': 29,
	'q': 59,
	'v': 79,
	'b': 3,
	'a': 2,
	's': 67,
	'm': 41,
	'e': 11,
	'l': 37,
	'u': 73,
	't': 71,
	'z': 101,
	'c': 5,
	'p': 53,
	'f': 13,
	'd': 7,
	'k': 31,
	'x': 89,
	'w': 83,
	'h': 19
}

Está desordenado, pero un dictionary, como los json, no están necesariamente ordenados. Acá cada letra tiene asignado un numero. Luego la función que calcula el numero para cada palabra:

def calculate_word(word):
    """
    Multiply the caracters of each word. Since every integer is a prime.
    Two words are anagram if their product is the same.
    """
    first = True
    total = 0
    for letter in word:
        number = d[letter]
        if first:
            first = False
            total = number
        else:
            total *= number
    return total

Esto es relativamente sencillo. Recorremos cada letra de la palabra y, por cada una de esas letras, buscamos su correspondiente numero primo en el diccionario y primero guardamos el numero y en la siguiente iteración multiplicamos con el siguiente numero primo/letra.


Tags