Posted by & filed under computación, matematica.

tumblr_lp3uyqxewl1qmo5kbo1_500

Hoy viajando hacia la facultad, recordé que Argentino era anagrama de Ignorante (si, hoy me desperté con mucho amor a la Patria…) y de inmediato me puse a pensar en cómo armar todas las combinaciones posibles con todas las letras de una palabra (que no necesariamente den otra palabra); y como calcular la cantidad de combinaciones dada la longitud de una palabra. Aclaro que no tomo en cuenta colisiones, es decir que para mi dos combinaciones de  xy son xy e yx indistintamente si x e y son o no iguales

1) Construyendo las combinaciones

Para ejemplificar el mecanismo de construcción voy a recurrir a un ejemplo sencillo cuya generalización debería ser trivial. Supongamos que tenemos la palabra xyz y debemos hayar todas las permutaciones posibles, primero debo establecer las primeras letras donde las posibilidades claramente son x-- ,y-- & z-- . En cada uno de estos casos debo completar -- con las combinaciones posibles de las letras restantes (acá ya deberías ir captando la onda).

Por ejemplo el x-- como restante deja la ‘palabra’ yz si repetimos el proceso (hasta que lógicamente nos quede una letra) obtenemos como permutaciones yz & zy; quedando como permutaciones posibles de xyz bajo el formato x-- xyz, xzy. Extendiendo a xyz obtenemos xyz, xzy, yxz, yzx, zxy, zyx.

Basicamente el algoritmo sería, por cada letra, añadir las combinaciones posibles con las letras restantes. Esto es un algoritmo recursivo. Aclaro que acá no se tienen en cuenta las colisiones ni si lo formado es o no una palabra, sino la cantidad de permutaciones posibles.

2) Calculo matemático

Ahora supongamos que el problema no radica en construir las permutaciones, sino calcular cuantas permutaciones posibles hay. Definamos P_{n} la función que dado un n (cantidad de letras) devuelva la cantidad de permutaciones posibles. Del mecanismo mencionado anteriormente, siendo que por cada letra (n) agrego las combinaciones posibles de las letras restantes, se obtiene que P_{n} = n * P_{n-1}, P_{1}=1. Esto es una relación de recurrencia, más precisamente en este caso es una función factorial y puede expresarse como P_{n} = n!

De aquí se desprende como aumenta la cantidad de permutaciones posibles con el aumento de letras y que lejos está de ser una relación lineal; por ejemplo hay 120 permutaciones posibles con 5 letras, pero con 10 las posibilidades están en el orden de los 4 millones. (ver nota más abajo)

3) Programación

Ahora veamos un ejemplo, escrito en Python:

Probando el programa:

alejandro@d-U10:~/python$ python ana.py
Ingrese palabra: ale
Los anagramas posibles son: \ ['ale', 'ael', 'lae', 'lea', 'eal', 'ela']
La cantidad es: 6

Comprobamos con cualquier calculadora que  fehacientemente 3!=3*2*1=6, otro ejemplo:

alejandro@d-U10:~/python$ python ana.py
Ingrese palabra: alejandro
La cantidad es: 362880

Otra vez verificamos que 9!=362880, por lógicas razones no puse los anagramas posibles, pero creanme que el programa los hace.

En este breve y sencillo post, se puede apreciar como detrás de un juego comúnmente encontrado en los libritos de pasatiempos, se pueden hacer apreciaciones y conclusiones muy interesantes.

Nota:

Mas arriba mencioné que la diferencia entre dos resultados, no era lineal; veamos porque. Supongamos dos números m,n \in N / m \neq n \land n-m=r, r \in N de acá sacamos que n! = n*(n-1)*(n-2)*...*(n-r)! siendo n-r=m obtengo n! = n*(n-1)*(n-2)*...*(n-r+1)*m! = n*(n-1)*(n-2)*...*(m+1)*m! con lo cual n! - m! = [n*(n-1)*(n-2)*...*(m+1)*m!] - m! despejando n! - m! = m! * [n*(n-1)*(n-2)*...*(m+1) - 1] ahora verifiquemos con los datos que ya tenemos. 3!=6 \land 9!=362880 entonces 9!-3! = 3! * [9*(9-1)*(9-2)*(9-3)*(9-4)*(9-5) -1] = 6 * [9*8*7*6*5*4-1] = 6 * [60480-1] = 6 * 60479 = 362874 que fehacientemente es 362880 - 6. Acá verificamos la ecuación dada con anterioridad y su no-linealidad es clara.

Actualización:

Como Python siempre apunta a la prolijidad (y todo programador debiera también), debo aclarar que hay una forma más ordenada de hacer lo mismo que el código expuesto:

Code

2 Responses to “Anagrama”

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos necesarios están marcados *