Obteniendo todas las posibles “palabras” de 7 letras (o menos)

Últimamente, el juego al que más le dedico tiempo (además de Tekken) es a Angry Words (apalabrados en español). Con eso que me gusta Scrabble desde hace mucho, me relaja mientras voy en el tren y al mismo tiempo me ayuda a practicar mi vocabulario.

De la misma manera, le he estado dedicando tiempo a aprender Haskell, ya que veo que algunas cosas de PLN podrían ser implementadas más fácilmente con programación funcional.

Buscaba un problema que me ayudara a practicar Haskell, a dar mis primeros pinitos en el lenguaje. Y mientras disfrutaba el mencionado juego y veía que es más de “ponle lo que sea a ver si pega” en vez de “piensa en alguna palabra interesante”, se me ocurrió crear un programa que, dada una serie de letras, mostrara todas la combinaciones posibles entre ellas. Lo veía fácil y factible, por lo que me decidí a poner manos a la obra.

¿Qué tan difícil puede ser?… me pregunté. Y aunque no es algo tan complicado, sí me tomó más tiempo del que pensaba debido a que había que hacer el cambio a programación funcional y no a imperativa.

Primero, a definir el algoritmo:

Tomemos una palabra de 3 letras (por conveniencia, más adelante verán por qué), digamos “ola”. ¿Qué es lo que quiero obtener? La lista de posibles permutaciones con esas 3 letras, es decir: ola, oal, loa, lao, aol, alo. Aquí me di cuenta de un patrón: tomo una letra de la palabra, la pongo al principio, y simplemente tomo las otras 2 letras restantes y les cambio el orden. Para comenzar, tomo la “o” como la letra principal, entonces me quedo con “la”, y las únicas combinaciones posibles son “la” y “al”; después, agrego la letra principal “o” y la pongo al principio de cada palabra, obteniendo “ola”,”oal”. Continúo con la siguiente letra, la “l”, la tomo como principal, quedándome “oa”, de la cual obtengo “oa” y “ao”; le pongo la “l” al principio de cada una y obtengo “loa”,”lao”. Por último tomo la “a” como letra principal, lo que me deja con “ol” como el resto, obteniendo “ol” y “lo”; le pongo la “a” al principio de cada una y resultan “aol”, “alo”. Juntando todos los resultados parciales, obtengo la lista de palabras que estoy buscando.

Con la definición anterior, recursivamente se pueden analizar palabras de cualquier longitud. ¿Buenas noticias para los que juegan apalabrados? En teoría, si es que tienen la paciencia de ver todos los resultados. ¿Cuántos son? Saquemos cuentas:

Una palabra de 3 letras resultó en una lista de 6 palabras. ¿Cuántas resultarán de una de 4? Como lo que buscamos son permutaciones, la fórmula es sencilla:

n!

Revisemos: 3! = 3x2x1 = 6. ¡Bien! Si cuadra el resultado

Entonces, con 4 letras tendremos: 4! = 4x3x2x1 = 24 Todavía no son muchas…

Con 5 : 5! = 5x4x3x2x1 = 120 ya da flojera ver tantas permutaciones…

¿Y con 7? Pues 7! = 7x6x5x4x3x2x1 = 5040 Está bien que no haya límite de tiempo en cada jugada de apalabrados, pero qué flojera (o ganas de ganar) de aquél(la) que se ponga a leerla cada vez.

¡Ajá! Dirán ustedes: ¿qué pasa si hay letras repetidas? Obviamente habrá palabras repetidas también, lo cual reduce nuestra lista. ¿A cuánto? Oh benditas matemáticas:

n!/(a!b!c!…)

En donde a es el número de veces que se repite una letra, b es el número de veces que se repite otra, c es el número de veces que se repite otra… y así sucesivamente.

Supongamos que tenemos las letras “atajada” (si las tienen, ¡no la piensen y jueguen esa palabra!). La letra “a” se repite 4 veces, entonces, tendremos:

7!/4! = 7x6x5 = 210

Quizá pude haber pensado el algoritmo con una palabra de 4 letras desde el principio, y aunque sí revisé a mano después, me era más fácil iniciar con una de 3 (sólo 6 posibles permutaciones).

Luego, a hacer el programa. El resultado, a sabiendas de que puede haber una mucho mejor implementación, es una belleza de 18 líneas de código (y porque puse doble enter en algunos lugares):

import Data.List
import System.Environment(getArgs)

main = do
  words <- getArgs
  processArguments words    

processArguments :: [String] -> IO ()
processArguments ws
  | length ws == 0 = putStrLn "Need a word to shuffle..."
  | length ws > 1 = putStrLn "Only a word per run..."
  | otherwise = mapM_ putStrLn $ shuffle $ head ws

shuffle :: String -> [String]
shuffle [] = []
shuffle (x:[]) = [[x]]
shuffle str@(x:y:[]) =  str : [reverse str]
shuffle (xs) = nub $ fst $ foldl (\acc c -> (fst acc ++ (map (++) $ shuffle $ snd acc ++ drop ((+1) . length $ snd acc) xs),  ++ snd acc)) ([],"") xs

Estoy casi seguro que tengo paréntesis de más, pero eso ya lo veré en futuros programas.

Sí. Es cierto que el código intimida al principio, sobre todo la última línea, que es la que hace el “trabajo sucio” en caso de ser necesario. Explico el código abajo, con la aclaración de que no comentaré esta vez sobre function composition, IO y valores monádicos en general:

shuffle es una función que recibe una palabra (String) y regresa una lista de palabras, que es la lista de todas las palabras posibles permutando las letras ([String]). Ahora bien, pensando en forma funcional, hay que definir qué es algo en vez de que cómo obtenerlo (y miren que todavía estoy muy verde en el tema), por lo que, sabiendo que un String es lo mismo que una lista de Char ([Char]):

shuffle de una lista vacía es una lista vacía.

shuffle de una palabra de una letra es una lista que contiene a la misma palabra.

shuffle de una palabra de 2 letras es una lista que contiene a la palabra y a su inverso (por ejemplo: shuffle de “la” sería [“la”,”al”]).

shuffle de una palabra de más de 2 letras es (y aquí vamos… agarren aire):

  1. La lista de elementos únicos incluidos en… (nub)
  2. el primer elemento de la tupla… (fst)
  3. obtenida de hacer la operación foldl a la palabra…
  4. usando como valor inicial una tupla de una lista vacía y una cadena vacía… ([],””)
  5. aplicando como función una abstracción lambda que toma el acumulador y el siguiente elemento a analizar de la lista… (\acc c ->)
  6. y regresa una tupla que contiene…
  7. como primer elemento, el primer elemento del acumulador (fst acc) concatenado con…
  8. la lista de palabras obtenida al…
  9. mapear  a la palabra original la función que agrega el carácter que está siendo analizado a cada una de las palabras obtenidas al… (map (++) … xs)
  10. aplicar shuffle a la palabra formada por el segundo elemento del acumulador (snd acc) concatenado con…
  11. la palabra formada por quitar los n+1 primeros caracteres de la palabra original…
  12. donde n = longitud de la palabra que haya en el segundo elemento del acumulador… (shuffle $ snd acc ++ drop (+1) . length $ snd acc)
  13. y como segundo elemento la palabra formado por unir el carácter que está siendo analizado con el segundo elemento del acumulador ( ++ snd acc)

Lo más difícil fue que se me ocurriera cómo llevar la cuenta de las letras ya revisadas, para que con cada pasada del foldl siempre revisara una palabra de longitud menor a la anterior. Sabiendo que el acumulador es el valor que regresa un fold, mi única opción era meter en él lo que ya había revisado sin alterar el resultado que debía devolver. De ahí la idea de una tupla.

Todo muy bonito, si, pero… ¿funciona? Compilemos y ejecutemos:

mmedina@yggdrasil-m:~$ ghc --make shuffle.hs
[1 of 1] Compiling Main             ( shuffle.hs, shuffle.o )
Linking shuffle ...

mmedina@yggdrasil-m:~$ ./shuffle ola
ola
oal
loa
lao
alo
aol

Al parecer todo bien. Esperaba 6 palabras en específico y las obtuve correctamente. Ahora con “hola”:

mmedina@yggdrasil-m:~$ ./shuffle hola
hola
hoal
hloa
hlao
halo
haol
ohla
ohal
olha
olah
oalh
oahl
loha
loah
lhoa
lhao
laho
laoh
aloh
alho
aolh
aohl
ahol
ahlo

Espero 24 palabras. Contemos…

mmedina@yggdrasil-m:~$ ./shuffle hola | wc -l
24

¿A poco pensaron que contaría a mano? Bueno, sí, sí lo hice la primera vez, jeje. Entonces, si pongo algo como “marinos”, 7 letras, no hay repetidas se supone que espero 5040 posibles permutaciones. ¿Será?

mmedina@yggdrasil-m:~$ ./shuffle marinos | wc -l
5040

¡Bien! Parece que todo está en orden. Y claro que no podía faltar el ejemplo de “atajada”: 7 letras, 1 de ellas repetida 4 veces = debo obtener 210 permutaciones. Veamos:

mmedina@yggdrasil-m:~$ ./shuffle atajada | wc -l
210

Por puro ocio, y con eso de que no tuve nada que hacer en el trabajo, me puse a implementar el mismo algoritmo en Java, tratando de mantener la forma de programar de forma funcional. Éste es el código:

package org.mmg.langcomp;

import java.util.HashSet;
import java.util.Set;

public class Shuffle {

	private static Set<String> shuffle (String word) {
		Set<String> words = new HashSet<String>();
		Set<String> newWords = new HashSet<String>();
		String newWord = "";
		String curChar = "";
		String revWord = "";
		String checked = "";

		switch (word.length()) {
			case 0:
				System.out.println("Nothing to add here");
				break;
			case 1:
				System.out.println("Length 1: Adding \"" + word + "\"");
				newWords.add(word);
				break;
			case 2:
				StringBuilder sb = new StringBuilder(word);
				revWord = sb.reverse().toString();
				System.out.println("Length 2: Adding \"" + word + "\" and its reverse: " + revWord);
				newWords.add(word);
				newWords.add(revWord);
				break;
			default:
				System.out.println("Length > 2: Adding \"" + word + "\"");
				newWords.add(word);

				for (int i = 0; i < word.length(); i++) {
					curChar = word.substring(i, i+1);
					newWord = "";
					words.clear();

					// New word to check
					newWord = checked + word.substring(i + 1);

					if (newWord.length() >= 2) {
						System.out.println("* Going to check \"" + newWord + "\"");

						words.addAll(shuffle(newWord));
						if (!words.isEmpty()) {
							System.out.println(words.size());
							for (String w : words) {
								System.out.println("Composing and adding \"" + (curChar + w) + "\"");
								newWords.add(curChar + w);
							}
						}
					}

					checked += curChar;
					System.out.println("Already checked chars: " + checked);

				} // for

		}

		return newWords;
	}

	public static void main (String a[]) {
		Set<String> words = null;

		if (a.length == 0) {
			System.out.println("Need a word to shuffle...");
			System.exit(1);
		}
		else if (a.length > 1) {
			System.out.println("Only a word per run...");
			System.exit(1);
		}
		else {
			words = shuffle(a[0]);
			for (String w : words) {
				System.out.println("+ " + w);
			}
		}

	}
}

 

A lo mejor se me fue algún detalle en la forma de programar, pero al menos compila. Noten que le tuve que poner println (me dio flojera implementar log4j o similares nada más para esto) para ir guiándome al momento de hacerlo y ver que entrara donde debía entrar.

Como pueden ver, la idea general no cambia. La diferencia radica en cómo se define lo que hace una función, y que en programación imperativa hay que, por lo general, escribir más (y dicen que cuanto más letras, la probabilidad de cometer errores aumenta). Probemos. Me tomaré la libertad de filtrar nada más los resultados (líneas que comienzan con “+”):

mmedina@yggdrasil-m:~$ java -cp ./bin org.mmg.langcomp.Shuffle hola | grep "^\+"
+ hloa
+ hola
+ halo
+ ohal
+ haol
+ oahl
+ ahol
+ lhao
+ lhoa
+ alho
+ olha
+ aolh
+ ahlo
+ laho
+ aohl
+ laoh
+ olah
+ loah
+ aloh
+ loha
+ oalh
+ hoal
+ hlao
+ ohla

Me da flojera contar a mano, así que:

mmedina@yggdrasil-m:~$ java -cp ./bin org.mmg.langcomp.Shuffle hola | grep "^\+" | wc -l
24

Se ve bien. Veamos con los demás casos:

mmedina@yggdrasil-m:~$ java -cp ./bin org.mmg.langcomp.Shuffle ola | grep "^\+" | wc -l
6
mmedina@yggdrasil-m:~$ java -cp ./bin org.mmg.langcomp.Shuffle marinos | grep "^\+" | wc -l
5040
mmedina@yggdrasil-m:~$ java -cp ./bin org.mmg.langcomp.Shuffle atajada | grep "^\+" | wc -l
210

Los números cuadran. Pero también sería bueno ver si hay diferencias con los resultados obtenidos con el programa en Haskell. Para eso, ordeno y guardo los resultados de ambos en archivos de texto para después aplicarles un diff. Gracias al ordenamiento, se supone que no debe haber diferencias entre los archivos. Probemos directamente con “marinos”. Un detalle nada más: como los resultados en Java comienzan con “+ “, les daré formato para que queden igual que los de Haskell (quitarles el signo de más y el espacio, dejando sólo a las palabras):

mmedina@yggdrasil-m:~$ java -cp ./bin org.mmg.langcomp.Shuffle marinos | grep "^\+" | tr -s -d "\+" "" | sed s/\\s//g | sort > results-java.txt
mmedina@yggdrasil-m:~$ ./shuffle marinos | sort > results-haskell.txt
mmedina@yggdrasil-m:~$ diff results-haskell.txt results-java.txt
mmedina@yggdrasil-m:~$

Si quieren ver si en realidad nada más hay una palabra de cada una, pueden hacer un cat | uniq -c | sort -n.

Obviamente esto dista mucho de ser un programa para hacer trampa en el juego. Para ello, habría que agregar un diccionario, filtrar las palabras que no estén en él para que solamente queden palabras válidas, pero también tendríamos que tomar en cuenta conjugaciones de verbos (que son permitidas en apalabrados). En resumen: sí, es un mini proyecto interesante. Quizá le dé seguimiento. Mi prioridad técnica (no de la especialidad) en este momento es programación funcional. De momento tengo suficiente con el buscador de formspring que nomás no me doy tiempo para terminar.

Se aceptan observaciones, correcciones y sugerencias 🙂

20 Replies to “Obteniendo todas las posibles “palabras” de 7 letras (o menos)”

  1. tssssssssssss aburridoooooooooooooo
    por eso deje prograaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa……………………………………………………………..nunca entendi

  2. Que genial, de que conoci Haskell en el primer semestre de la carrera me ha encantado y lo uso para todo tipo de “duda rápida”. Es mucho más sencillo programar muchas cosas en haskell que en java .

  3. Hola, yo de nuevo. Estaba jugando draw something y no tenía idea de qué me habían dibujado así que recurrí a tu programa para buscar la palabra adecuada.

    Ejecuté tu código con el intérprete de Hugs
    Main> shuffle “iedargcb”

    Y funcionó extraordinariamente lento. Lo tuve corriendo unos veinte minutos y no terminó de darme todas las combinaciones. Al final resultó que la palabra que buscaba era birdcage.

    En fin, la verdad es que no leí tu código y mucho menos calculé su complejidad, pero tomo nota para hacerlo en cuanto me sea posible. Mientras tanto crees que corra tan lento porque use un intérprete en lugar de compilarlo?

    1. Hola Diego.
      Depende también de la máquina donde lo hayas corrido, pero en general esta implementación en Haskell es más lenta que la de Java.
      Corrí el programa en Haskell con la palabra que pusiste y medí el tiempo. Tardó exactamente un minuto en terminar, aunque sí, yo lo compilé e hice el ejecutable. Corrí la versión de Java también, y ésta tardó unos 10-15 segundos en terminar. Considerando que la palabra tiene 8 letras y que hay 40320 posibles permutaciones, creo que ambas versiones son relativamente lentas.

      Ahora bien, sé que hay mejores implementaciones que la que yo hice, sobre todo en Haskell. Ten en cuenta que apenas estoy en pañales en ese lenguaje y hay mucho que mejorar. En cuanto a la de Java, necesitaría sentarme a rehacer el algoritmo de otra forma, pues lo hice cuidando que fuera una implementación similar a la de Haskell.

      Lo que sí hice en estos días fue ponerle un diccionario (en español) a la versión de Java, y ahora te regresa solamente las palabras que sean válidas en el lenguaje. Cierto es que tarda más, pero los resultados son mucho más exactos.

      En todo caso, si tienes chance de checar la versión de Haskell, adelante 🙂 Yo también en una oportunidad veré cómo mejorar el tiempo de ejecución.

      Saludos, y gracias por tus comentarios.

  4. hola! nunca había usado el compilador de haskell hasta ahora. Me sorprendió demasiado lo rápido que es el compilador comparado con el intérprete de hugs. Me dio todas las combinaciones para la misma palabra en poco más de un minuto, con un procesador amd phenom 9950 a 2.5 ghz.

    A partir de ahora me voy a dedicar a aprender a fondo Haskell. Para esto estoy leyendo un libro Real World Haskell que se ve muy interesante. Tú qué has leido?

  5. Learn you a Haskell. Es quizá el mejor libro que existe para aprender Haskell.

    Yo también comencé con Real World Haskell. El libro es bueno, pero siento que Learn you a Haskell hace una mucho mejor introducción a los conceptos de programación funcional. Yo diría que Real World Haskell debería ser el segundo que leyeras.

    Haskell es muy chido, bonito y elegante, pero son pocas las empresas que lo usan comercialmente. De todas formas, aprender los conceptos de programación funcional te ayuda a mejorar tus técnicas de programación en cualquier otro lenguaje. Yo en lo personal adoro los Monads desde que los entendí 🙂

  6. según yo, ya tengo un conocimiento básico del lenguaje y del paradigma. En primer semestre lo vimos para entender la recursión e hicimos algunas prácticas sobre listas y árboles. Ahora estoy llevando una materia de análisis lógico y las prácticas son usando haskell y prolog.

    La verdad es que de momento todavía no me siento competente en ningún lenguaje de programación y como dices, Haskell es muy elegante y compacto. Cuando vi que quicksort se escribía en dos lineas quedé fascinado.

    En fin, quiero dominar Haskell, y creo que seguiré leyendo el Real World a ver hasta dónde llego. Ahí te cuento luego jeje

    qs [] = []
    qs (x:xs) = (qs [a|a<x, a=x, b <- xs])

    Si eso no es belleza, entonces no existe la belleza xD

  7. HOLA. SABES SI HAY EN INTERNET, ALGÚN SITIO DONDE YA EXISTA EL PROGRAMA. DONDE SE PUEDA INTRODUCIENDO UNA PALABRA, OBTENER LA LISTA D TODAS LAS PERMUTACIONES D SUS LETRAS?

  8. ¿Conoce alguien alguna web que haga esto? O sea, tu pones las letras y la web te da todas las combinaciones posibles de estas letras.
    Gracias. ^_^

  9. Hola! no se programar, llevo cerca de 2 horas tratando de encontrar un programa que me ayude a realizar todo esto, pero solo he encontrado cosas muy complejas de algoritmos de permutación y shuffle, me gustaría poder encontrar un programa ya terminado para poder usarlo, por favor, me sería de mucha ayuda ya que quiero hacer anagramas. Ayuda porfa! Gracias y buen día : )

    1. ¡Holas!

      El código que está aquí funciona. Es nada más cuestión de compilarlo para que después lo puedes ejecutar. En Haskell hay una forma más sencilla de hacerlo (mucho más que la que escribí aquí).

      Te recomiendo que agarres el código en Java, lo compiles y lo uses.

      ¡Saludos!

  10. #Les dejo mi solucion hecha en Python, por ahi a alguien le sirve.

    def main():
    cadenaOrig = raw_input(” Ingrese la cadena : “)
    cadena = cadenaOrig.lower()
    listaD = []
    auxiliar = “”
    permutar(cadena,auxiliar,listaD)
    print len(listaD)

    def permutar(cad,aux,lis):
    for i in cad:
    cad1=restarChar(cad,i)
    op = aux+i
    if len(cad1)==0:
    if not op in lis:
    lis.append(op)
    print op
    else:
    permutar(cad1,op,lis)

    def restarChar(cadena,char):
    cadRes=””
    for g in cadena:
    if not char == g:
    cadRes += g
    else:
    char = “”
    return cadRes

    main()

    1. Vuelvo a colocar el fuente pero reemplazando los tabs por “-” para que se comprenda mejor.

      def main():
      – cadenaOrig = raw_input(” Ingrese la cadena : “)
      – cadena = cadenaOrig.lower()
      – listaD = []
      – auxiliar = “”
      – permutar(cadena,auxiliar,listaD)
      – print len(listaD)

      def permutar(cad,aux,lis):
      – for i in cad:
      — cad1=restarChar(cad,i)
      — op = aux+i
      — if len(cad1)==0:
      — if not op in lis:
      —- lis.append(op)
      —- print op
      — else:
      — permutar(cad1,op,lis)

      def restarChar(cadena,char):
      – cadRes=””
      – for g in cadena:
      — if not char == g:
      — cadRes += g
      — else:
      — char = “”
      – return cadRes

      main()

Leave a Reply to Manuel Cancel reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.