algorithm - codigo - anagrama algoritmo

Algoritmo para generar anagramas (14)

Cuál sería la mejor estrategia para generar anagramas.

An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once; ex.
Once más dos es un anagrama de Doce más uno
Un punto decimal es un anagrama de Soy un punto en su lugar
Los astrónomos son anagramas de los observadores de la Luna

Al principio, parece sencillo, simplemente revolver las letras y generar todas las combinaciones posibles. Pero, ¿cuál sería el enfoque eficiente para generar solo las palabras en el diccionario?

Encontré esta página, Resolviendo anagramas en Ruby .

Pero, ¿cuáles son tus ideas?

Como Jason sugirió, prepare un diccionario haciendo hashtable con la palabra clave ordenada alfabéticamente, y la palabra de valor en sí (puede tener múltiples valores por tecla).
Elimine los espacios en blanco y ordene su consulta antes de buscarla.

Después de esto, necesitarías hacer una especie de búsqueda recursiva y exhaustiva. El pseudo código es muy aproximado:

function FindWords(solutionList, wordsSoFar, sortedQuery) // base case if sortedQuery is empty solutionList.Add(wordsSoFar) return // recursive case // InitialStrings("abc") is {"a","ab","abc"} foreach initialStr in InitalStrings(sortedQuery) // Remaining letters after initialStr sortedQueryRec := sortedQuery.Substring(initialStr.Length) words := words matching initialStr in the dictionary // Note that sometimes words list will be empty foreach word in words // Append should return a new list, not change wordSoFar wordsSoFarRec := Append(wordSoFar, word) FindWords(solutionList, wordSoFarRec, sortedQueryRec)

Al final, necesita iterar a través de la lista de soluciones e imprimir las palabras en cada sublista con espacios entre ellas. Es posible que deba imprimir todos los pedidos para estos casos (por ejemplo, "Yo soy Sam" y "Sam soy" son ambas soluciones).

Por supuesto, no probé esto, y es un enfoque de fuerza bruta.

Así que here''s la solución de trabajo, en Java, que Jason Cohen sugirió y funciona un poco mejor que la que usa trie. A continuación se encuentran algunos de los puntos principales:

Solo cargue el diccionario con las palabras que son subconjuntos del conjunto de palabras dado
El diccionario será un hash de palabras ordenadas como clave y un conjunto de palabras reales como valores (como lo sugirió Jason)
Itere a través de cada palabra de la clave del diccionario y realice una búsqueda recursiva hacia adelante para ver si se encuentra un anagrama válido para esa clave
Solo haga la búsqueda directa porque ya se han encontrado anagramas para todas las palabras que ya han sido atravesadas.
Fusiona todas las palabras asociadas a las teclas para, por ejemplo, si ''alista'' es la palabra para la cual se encuentran los anagramas y uno de los conjuntos para fusionar es [ins] y [elt], y las palabras reales para la tecla [ins ] es [sin] y [ins], y para la clave [elt] es [let], entonces el conjunto final de palabras de fusión sería [sin, let] y [ins, let], que formarán parte de nuestra lista final de anagramas
Además, para tener en cuenta que, esta lógica solo mostrará un conjunto único de palabras, es decir, "once más dos" y "dos más once" serían iguales y solo uno de ellos se enumeraría en la salida

A continuación se muestra el código recursivo principal que encuentra el conjunto de claves de anagrama:

// recursive function to find all the anagrams for charInventory characters // starting with the word at dictionaryIndex in dictionary keyList private Set<Set<String>> findAnagrams(int dictionaryIndex, char[] charInventory, List<String> keyList) { // terminating condition if no words are found if (dictionaryIndex >= keyList.size() || charInventory.length < minWordSize) { return null; } String searchWord = keyList.get(dictionaryIndex); char[] searchWordChars = searchWord.toCharArray(); // this is where you find the anagrams for whole word if (AnagramSolverHelper.isEquivalent(searchWordChars, charInventory)) { Set<Set<String>> anagramsSet = new HashSet<Set<String>>(); Set<String> anagramSet = new HashSet<String>(); anagramSet.add(searchWord); anagramsSet.add(anagramSet); return anagramsSet; } // this is where you find the anagrams with multiple words if (AnagramSolverHelper.isSubset(searchWordChars, charInventory)) { // update charInventory by removing the characters of the search // word as it is subset of characters for the anagram search word char[] newCharInventory = AnagramSolverHelper.setDifference(charInventory, searchWordChars); if (newCharInventory.length >= minWordSize) { Set<Set<String>> anagramsSet = new HashSet<Set<String>>(); for (int index = dictionaryIndex + 1; index < keyList.size(); index++) { Set<Set<String>> searchWordAnagramsKeysSet = findAnagrams(index, newCharInventory, keyList); if (searchWordAnagramsKeysSet != null) { Set<Set<String>> mergedSets = mergeWordToSets(searchWord, searchWordAnagramsKeysSet); anagramsSet.addAll(mergedSets); } } return anagramsSet.isEmpty() ? null : anagramsSet; } } // no anagrams found for current word return null; }

Puede bifurcar el repositorio desde here''s y jugar con él. Hay muchas optimizaciones que podría haber perdido. Pero el código funciona y encuentra todos los anagramas.

Cómo lo veo:

querrías construir una tabla que mapee conjuntos de letras desordenadas para enumerar palabras, es decir, pasar por el diccionario para que termines con, digamos

lettermap[set(a,e,d,f)] = { "deaf", "fade" }

luego, a partir de tu palabra de inicio, encuentras el conjunto de letras:

astronomers => (a,e,m,n,o,o,r,r,s,s,t)

luego recorra todas las particiones de ese conjunto (esta podría ser la parte más técnica, generando todas las particiones posibles) y busque las palabras para ese conjunto de letras.

editar: hmmm, esto es más o menos lo que Jason Cohen publicó.

editar: además, los comentarios sobre la pregunta mencionan la generación de anagramas "buenos", como los ejemplos :). después de que construyas tu lista de todos los anagramas posibles, ejecútalos a través de WordNet y encuentra los que están semánticamente cerca de la frase original :)

El libro Programming Pearls de Jon Bentley cubre este tipo de cosas bastante bien. Una lectura obligada.

Hace un tiempo escribí una publicación en un blog sobre cómo encontrar rápidamente dos anagramas de palabras. Funciona muy rápido: encontrar los 44 anagramas de dos palabras para una palabra con un archivo de texto de más de 300,000 palabras (4 Megabytes) toma solo 0.6 segundos en un programa de Ruby.

Algoritmo del Buscador de Anagramas de Dos Palabras (en Ruby)

Es posible hacer que la aplicación sea más rápida cuando se permite preprocesar la lista de palabras en una gran asignación de hash, desde palabras ordenadas por letras a una lista de palabras que utilizan estas letras. Estos datos preprocesados se pueden serializar y usar a partir de ese momento.

He usado la siguiente forma de calcular anagramas hace un par de meses:

Calcule un "código" para cada palabra en su diccionario: cree una tabla de búsqueda a partir de letras en el alfabeto para números primos, por ejemplo, comenzando con [''a'', 2] y terminando con [''z'', 101]. Como paso de procesamiento previo, calcule el código de cada palabra en su diccionario buscando el número primo para cada letra en el que consiste en la tabla de búsqueda y multiplíquelas juntas. Para una búsqueda posterior crea una multimapa de códigos para palabras.
Calcule el código de su palabra de entrada como se describe arriba.
Compute codeInDictionary% inputCode para cada código en el multimap. Si el resultado es 0, ha encontrado un anagrama y puede buscar la palabra adecuada. Esto también funciona para anagramas de 2 o más palabras.

Espero que haya sido útil.

La mayoría de estas respuestas son terriblemente ineficientes y / o solo darán soluciones de una palabra (sin espacios). Mi solución manejará cualquier número de palabras y es muy eficiente.

Lo que quieres es una estructura de datos trie. Aquí hay una implementación completa de Python. Solo necesita una lista de palabras guardada en un archivo llamado words.txt . Puede probar la lista de palabras del diccionario de Scrabble aquí:

http://www.isc.ro/lists/twl06.zip

MIN_WORD_SIZE = 4 # min size of a word in the output class Node(object): def __init__(self, letter='''', final=False, depth=0): self.letter = letter self.final = final self.depth = depth self.children = {} def add(self, letters): node = self for index, letter in enumerate(letters): if letter not in node.children: node.children[letter] = Node(letter, index==len(letters)-1, index+1) node = node.children[letter] def anagram(self, letters): tiles = {} for letter in letters: tiles[letter] = tiles.get(letter, 0) + 1 min_length = len(letters) return self._anagram(tiles, [], self, min_length) def _anagram(self, tiles, path, root, min_length): if self.final and self.depth >= MIN_WORD_SIZE: word = ''''.join(path) length = len(word.replace('' '', '''')) if length >= min_length: yield word path.append('' '') for word in root._anagram(tiles, path, root, min_length): yield word path.pop() for letter, node in self.children.iteritems(): count = tiles.get(letter, 0) if count == 0: continue tiles[letter] = count - 1 path.append(letter) for word in node._anagram(tiles, path, root, min_length): yield word path.pop() tiles[letter] = count def load_dictionary(path): result = Node() for line in open(path, ''r''): word = line.strip().lower() result.add(word) return result def main(): print ''Loading word list.'' words = load_dictionary(''words.txt'') while True: letters = raw_input(''Enter letters: '') letters = letters.lower() letters = letters.replace('' '', '''') if not letters: break count = 0 for word in words.anagram(letters): print word count += 1 print ''%d results.'' % count if __name__ == ''__main__'': main()

Cuando ejecuta el programa, las palabras se cargan en un trie en la memoria. Después de eso, simplemente escriba las letras con las que desea buscar e imprimirá los resultados. Solo mostrará los resultados que usan todas las letras de entrada, nada más corto.

Filtra palabras cortas de la salida, de lo contrario, la cantidad de resultados es enorme. Siéntase libre de modificar la configuración MIN_WORD_SIZE . Tenga en cuenta que solo usa "astrónomos" ya que la entrada da 233,549 resultados si MIN_WORD_SIZE es 1. Quizás pueda encontrar una lista de palabras más corta que solo contenga palabras en inglés más comunes.

Además, la contracción "Yo soy" (de uno de sus ejemplos) no se mostrará en los resultados a menos que agregue "im" al diccionario y establezca MIN_WORD_SIZE en 2.

El truco para obtener varias palabras es volver al nodo raíz en el trie siempre que encuentre una palabra completa en la búsqueda. Luego sigues atravesando el trie hasta que se hayan utilizado todas las letras.

Para cada palabra en el diccionario, ordena las letras alfabéticamente. Entonces "foobar" se convierte en "abfoor".

Luego, cuando ingrese el anagrama de entrada, ordene sus letras también, luego búsquelo. ¡Es tan rápido como una búsqueda de hashtable!

Para palabras múltiples, puede hacer combinaciones de letras ordenadas, ordenando sobre la marcha. Aún mucho más rápido que generar todas las combinaciones.

(ver comentarios para más optimizaciones y detalles)

Por fuera de mi cabeza, la solución que tiene más sentido sería elegir una letra de la cadena de entrada de forma aleatoria y filtrar el diccionario en función de las palabras que comienzan con eso. Luego seleccione otro, filtre en la segunda letra, etc. Además, filtre las palabras que no se pueden hacer con el texto restante. Luego, cuando tocas el final de una palabra, inserta un espacio y comienza con las letras restantes. También puede restringir las palabras según el tipo de palabra (por ejemplo, no tendría dos verbos al lado del otro, no tendría dos artículos al lado del otro, etc.).

Preproceso:

Construya un trie con cada hoja como una palabra conocida, en orden alfabético.

En el tiempo de búsqueda:

Considere la cadena de entrada como un conjunto múltiple. Encuentre la primera palabra secundaria atravesando el índice trie como en una búsqueda en profundidad. En cada sucursal puede preguntar: ¿está la letra x en el resto de mi entrada? Si tiene una buena representación de múltiples conjuntos, esta debería ser una consulta de tiempo constante (básicamente).

Una vez que tenga la primera palabra secundaria, puede mantener el resto en forma múltiple y tratarlo como una nueva entrada para encontrar el resto de ese anagrama (si existe).

Aumente este procedimiento con memoialización para consultas más rápidas en multiempaturas de resto común.

Esto es bastante rápido: cada trie transversal está garantizado para dar una subpalabra real, y cada recorrido toma un tiempo lineal en la longitud de la subpalabra (y las subwords generalmente son bastante pequeñas, según los estándares de codificación). Sin embargo, si realmente quieres algo aún más rápido, podrías incluir todos los n-grams en tu proceso previo, donde un n-gram es cualquier cadena de n palabras seguidas. Por supuesto, si W = #words, pasará del tamaño de índice O (W) a O (W ^ n). Quizás n = 2 es realista, dependiendo del tamaño de tu diccionario.

Si tomo un diccionario como un Hash Map ya que cada palabra es única y la clave es una representación binaria (o hexadecimal) de la palabra. Entonces, si tengo una palabra, puedo encontrar fácilmente el significado con O (1) complejidad.

Ahora, si tenemos que generar todos los anagramas válidos, necesitamos verificar si el anagrama generado está en el diccionario, si está presente en el diccionario, es válido, de lo contrario debemos ignorarlo.

Asumiré que puede haber una palabra de un máximo de 100 caracteres (o más, pero hay un límite).

Entonces, cualquier palabra que tomemos como una secuencia de índices como una palabra "hola" puede representarse como "1234". Ahora los anagramas de "1234" son "1243", "1242" ..etc

Lo único que debemos hacer es almacenar todas esas combinaciones de índices para un número particular de caracteres. Esta es una tarea de una sola vez. Y luego se pueden generar palabras a partir de las combinaciones eligiendo los caracteres del índice. Por lo tanto, obtenemos los anagramas.

Para verificar si los anagramas son válidos o no, simplemente indexe en el diccionario y valide.

Lo único que se debe manejar son los duplicados. Esto se puede hacer fácilmente. Como cuando necesitamos comparar con los anteriores que se han buscado en el diccionario.

La solución enfatiza en el rendimiento.

Uno de los trabajos fundamentales sobre anagramas programáticos fue realizado por Michael Morton (Sr. Machine Tool), utilizando una herramienta llamada Ars Magna. Aquí hay un artículo ligero basado en su trabajo.

Vea esta assignment del departamento de CSE de la Universidad de Washington.

Básicamente, tienes una estructura de datos que solo tiene los recuentos de cada letra en una palabra (una matriz funciona para ascii, actualiza a un mapa si quieres compatibilidad con Unicode). Puedes restar dos de estos conjuntos de letras; si un recuento es negativo, usted sabe que una palabra no puede ser un anagrama de otra.

Y here está mi solución novedosa.

El libro de Jon Bentley Programming Pearls contiene un problema para encontrar anagramas de palabras. La declaración:

Dado un diccionario de palabras en inglés, encuentre todos los conjuntos de anagramas. Por ejemplo, "pots", "stop" y "tops" son todos anagramas el uno del otro porque cada uno se puede formar permutando las letras de los demás.

Pensé un poco y se me ocurrió que la solución sería obtener la firma de la palabra que está buscando y compararla con todas las palabras del diccionario. Todos los anagramas de una palabra deben tener la misma firma. Pero, ¿cómo lograr esto? Mi idea era usar el teorema fundamental de la aritmética:

El teorema fundamental de la aritmética establece que

cada entero positivo (excepto el número 1) se puede representar exactamente en una dirección aparte de la reorganización como producto de uno o más números primos

Entonces, la idea es usar una matriz de los primeros 26 números primos. Luego, para cada letra de la palabra obtenemos el número primo correspondiente A = 2, B = 3, C = 5, D = 7 ... y luego calculamos el producto de nuestra palabra de entrada. A continuación hacemos esto para cada palabra en el diccionario y si una palabra coincide con nuestra palabra de entrada, la agregamos a la lista resultante.

El rendimiento es más o menos aceptable. Para un diccionario de 479828 palabras, se necesitan 160 ms para obtener todos los anagramas. Esto es aproximadamente 0,0003 ms / palabra, o 0.3 microsegundo / palabra. La complejidad del algoritmo parece ser O (mn) o ~ O (m) donde m es el tamaño del diccionario yn es la longitud de la palabra de entrada.

Aquí está el código:

package com.vvirlan; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.Date; import java.util.List; import java.util.Scanner; public class Words { private int[] PRIMES = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113 }; public static void main(String[] args) { Scanner s = new Scanner(System.in); String word = "hello"; System.out.println("Please type a word:"); if (s.hasNext()) { word = s.next(); } Words w = new Words(); w.start(word); } private void start(String word) { measureTime(); char[] letters = word.toUpperCase().toCharArray(); long searchProduct = calculateProduct(letters); System.out.println(searchProduct); try { findByProduct(searchProduct); } catch (Exception e) { e.printStackTrace(); } measureTime(); System.out.println(matchingWords); System.out.println("Total time: " + time); } private List<String> matchingWords = new ArrayList<>(); private void findByProduct(long searchProduct) throws IOException { File f = new File("/usr/share/dict/words"); FileReader fr = new FileReader(f); BufferedReader br = new BufferedReader(fr); String line = null; while ((line = br.readLine()) != null) { char[] letters = line.toUpperCase().toCharArray(); long p = calculateProduct(letters); if (p == -1) { continue; } if (p == searchProduct) { matchingWords.add(line); } } br.close(); } private long calculateProduct(char[] letters) { long result = 1L; for (char c : letters) { if (c < 65) { return -1; } int pos = c - 65; result *= PRIMES[pos]; } return result; } private long time = 0L; private void measureTime() { long t = new Date().getTime(); if (time == 0L) { time = t; } else { time = t - time; } } }