LeaTex escribió:Acá les traigo un problema que tengo esta semana dando vueltas, y quisiera ver sus opiniones (o si me dan la solución, joya).
Recuerden que trabajo con Smalltalk, así que todo en objetos.
En fin, dada una cadena de 6 caracteres, necesito encontrar la mayor cantidad de palabras que puedo armar con esos 6 caracteres, que tengan entre 3 y 6 letras.
Ej: 'abejot'
- tejo
- jota
- jeta
- bea
- beta
- toba
etc...
Mi primera idea es generar todas las combinaciones posibles de 3 caracteres, de 4, de 5 y de 6. Y comparar contra un diccionario.
Lo malo es que las combinatorias son lentas, y además voy a estar produciendo una gran cantidad de info que no me va a servir cuando las filtre. Pero no se me ocurre nada más.
Además: ¿Cómo hago las combinaciones de 6? El resultado es un 6! y lo primero que se me viene a la mente son 6 ciclos anidados, ¿no?
No importa si usas objetos o no, la lógica a aplicar tiene que ser la misma, es más bien un problema de ingenio.
Voy a mostrar como saber CUÁNTAS, y por otro lado, CUÁLES palabras podés formar.
Las palabras tienen que tener sentido? Si no lo tienen que tener, sólo necesitas calcular la combinatoria, como hacíamos en proba. Esto es para
saber CUÁNTAS son:
cantidadTotal = cantidadCon3 + cantidadCon4 + cantidadCon5 + cantidadCon6
Las letras se pueden repetir? eso es importante, porque la cantidad puede variar mucho, pero supongo que NO.
Sabemos que el orden SÍ importa, ya que mismas letras pero diferente orden forman otra palabra.
Pensalo así para cantidad de 3: uno toma una letra de las 6, y se queda con 5. Ahora tomas una de las 5, y te quedas con 4. Ahora una de las 4, y te quedás con 3.
O sea, podés tomar: 6*5*4 variaciones posibles, o lo que es lo mismo 6*5*4*3*2*1 / 3*2*1 = 6! / 3!.
En general, la fórmula es: n! / (n-k)!, siendo n la cantidad de letras total y k la cantidad de letras que usas.
O sea que la cantidadTotal te queda:
cantidadTotal = 6!/3! + 6!/2! + 6!/1! + 6!/0!
Eso para averiguar la cantidad... la función factorial no es difícil de hacer, pero si la querès hacer eficiente para no repetir cálculos hay que pensarla un cacho más.
Igual, supongo que lo más importante para vos es averiguar QUÉ palabras se pueden formar...
EDIT: ahí lei que pusiste que tienen que tener sentido... igualmente, esta cantidad te sirve para saber todas las iteraciones que tu programa tendría que hacer si querés generar tooodas las palabras y comparar con un diccionario. Vos lo dijiste: los problemas de combinatoria suelen ser poco eficientes... evidentemente, hay que pensar otra alternativa.
SOLUCIÓN POSIBLE
Lo más eficiente en este caso, es
ARMAR UN ÁRBOL, donde las hojas sean las posibles palabras (en un diccionario o no), y los nodos intermedios los pasos necesarios para formarlas. Vamos a ver después que el árbol incluso es
CONCEPTUAL, o sea, que nunca se crea realmente, pero el concepto está aplicado.
Entonces, la raíz no tiene ninguna letra, pero tiene 6 hijas, en el ejemplo: "a", "b", "e", "j", "o", "t". Ahora, la "a" tiene 5 hijas, "b", "e", "j", "o", "t". La "b" que es hija de la "a" tiene 4 hijas: "e", "j", "o", "t"... y así, hasta que sólo se pueda tener una hija (la hoja).
No te conviene guardar la subcadena en el nodo, o sea, guardar "a" en el 1º nivel y en el segundo guardar "ab", "ae", etc... porque lo podés armar en el momento y eso consumiría bastante más memoria. Parece tonto pensar en memoria usada, pero es realmente mucha, pensá la cantidad de nodos que necesitás... 6 nodos para las primeras letras, 6*5 para las segundas, 6*5*4 para tercera profundidad, y así hasta llegar a las hojas, donde tendrías 6!. Igualmente, esto es sólo si generás el árbol en memoria, ahora que lo pienso mejor, ni siquiera sería necesario
.
Como verás, este árbol sólo puede tener como máxima profundidad 7 (contando la raíz que no tiene letra asignada), por lo cual recorrerlo sólo lleva 6 pasos como máximo. Si bien recorrerlo para cada palabra llevaría la misma cantidad de iteraciones (y más, para los pasos intermedios antes de llegar a las hojas), se puede usar técnicas de descarte ("Branch & Bound" se llama, si no me equivoco) en la que uno vaya descartando aquellas ramas que ya sabe que no le resultan útiles.
Por ejemplo, tenés un diccionario con palabras posibles, y tenés tu árbol con las letras cargadas (conceptual, o realmente en memoria). Cuando vos descendés en una rama del árbol, en el diccionario te estás posicionando. Avanzás otra vez más, y te reposicionás. Van a llegar puntos donde ciertas ramas no te permitan reposicionarte. Por ejemplo:
Tomás la "a", y te posicionás en el dic en la letra "a".
Tomás la "b" (avanzás en el árbol), y te posicionás en el dic donde empieza "ab".
Tomás la "j" (después de haber probado con las otras letras), y te posicionás en donde empiezan palabras con "abj"...
Pero qué pasa? No tenés palabras que empiecen así! Entonces sabés que no tiene sentido avanzar por los hijos de ese nodo, o sea que te ahorrás, en ese paso, 3*2*1 = 6 nodos para leer. Es lo que se dice como "podar una rama del árbol". Parece poco, pero pensá que si empezás con "t" y luego vas a la "b", ahí te ahorrás 4*3*2*1 = 24 nodos, y también con "tj", etc, por lo cual la cantidad de palabras que evitás procesar y generar (por ejemplo, escribiendolas en una colección, en un archivo, etc.), es mucho menor, y el programa es más eficiente.
Por qué digo que no tenés que crear el árbol? Porque el árbol es muy útil para visualizar el problema, pero irrelevante a la hora de moverte en el diccionario. Saber que nos movemos según un árbol nos indica que el algoritmo tiene cierta tendencia logarítmica (mientras que los problemas resueltos a fuerza bruta con combinatoria tienen una tendencia de complejidad factorial, y eso es muchísimo menos eficiente, que me corrija alguien si sabe esto mejor).
Eso sí, hay que tener en cuenta una cosa: no es necesario llegar al final para formar una palabra, con llegar a 3 letras ya podemos ir encontrando.
Una implementación más o menos sensata, en pseudocódigo:
Procedimiento/Función/Método: FormarPalabras(Subcadena)
1) Si Subcadena tiene 3 o más letras:
1.a) Si está en el diccionario:
1.b) Procesar(Subcadena).
1.c) Si NO está en el diccionario, volver en el stack (return... esto es, básicamente, "podar la rama", ya que no se procesa nada por debajo de esta rama, ya que no se ejecuta el bucle 3).
2) Si Subcadena tiene 6 letras, volver en el stack al procedimiento/función/método que llamó, para que se prueben otras combinaciones (vulgarmente, hacer un "return" 
- creo que no necesitarías devolver ningún valor).
3) De 1 a 6, hacer: (o de 0 a 5, según implementación)
3.a) De un conjunto de 6 letras ordenadas, tomás la letra(i).
3.b) Llamás a FormarPalabras(Subcadena concatenada con la letra(i)).
4) Fin FormarPalabras.
"Procesar" es un p/f/método que hace lo que vos necesitás hacer con la palabra, por ejemplo, mostrarla en pantalla, imprimirla en un archivo, agregarlas a otro diccionario (que sería mucho menor, ya que sólo tendría las palabras formadas con esas 6 letras).
Sobre implementaciones: el conjunto de 6 letras no necesita realmente estar ordenado. Conviene que esté ordenado si las letras se mantienen en el conjunto. La otra es pasar en cada llamado a "FormarPalabras" un nuevo conjunto con las 6 letras, y que a medida que se usan se vayan eliminando del conjunto, hasta que esté vacío. Sin embargo, pasar ese nuevo conjunto en cada llamada complica las cosas innecesariamente, por eso la opción del vector (o de alguna colección que posea orden, en este caso, un Set o Bag no servirían, sí una OrderedCollection -no me acuerdo mucho de los nombres de Smalltalk igual-).
Después hasta se pueden sacar estadísticas interesantes, onda: ver cuantas palabras reales existen sobre la cantidad total que se pueden formar (no puedo evitarlo, son esas dudas existenciales que siempre tuve ¿¿??).
Bueno, espero que te sirva, a mí me parece una solución válida... capaz hay que retocarla un poco, pero tiene sentido y es mucho más eficiente que hacer la combinatoria y luego comparar (que exigiría mucho espacio en memoria para generar todas las palabras, y tiempo para generarlas y encima luego buscarlas en el diccionario).
Saludos!!
![[-]](images/collapse.gif)
.gif "=)")
Un reconocedor de letras utilizando RNA (redes neuronales artificiales) 
). Turno noche, of course 
![[Imagen: frase.png]](https://frasesdelea.000webhostapp.com/frase.png)
