Genera todas las combinaciones posibles de letras en una palabra

 function allAnagrams (word) { if (word.length < 2) { return [word]; } else { var allAnswers = []; for (var i = 0; i < word.length; i++) { var letter = word[i]; var shorterWord = word.substr(0, i) + word.substr(i + 1, word.length - 1); var shortwordArray = allAnagrams(shorterWord); for (var j = 0; j < shortwordArray.length; j++) { allAnswers.push(letter + shortwordArray[j]); } } return allAnswers; } } allAnagrams("") 

Voy a lanzar mi sombrero en el ring con la versión iterativa del método Heap de generar permutaciones. Me tomó un tiempo hacerlo bien, ya que mi fuente de referencia tiene un error tipográfico en el algoritmo -_-.

function swap(chars, i, j) { var tmp = chars[i]; chars[i] = chars[j]; chars[j] = tmp; } function getAnagrams(input) { var counter = [], anagrams = [], chars = input.split(""), length = chars.length, i; for (i = 0; i < length; i++) { counter[i] = 0; } anagrams.push(input); i = 0; while (i < length) { if (counter[i] < i) { swap(chars, i % 2 === 1 ? counter[i] : 0, i); counter[i]++; i = 0; anagrams.push(chars.join("")); } else { counter[i] = 0; i++; } } return anagrams; } 

Con algunos tiempos de muestra para contar los anagramas de «codereview»:

$ time node anagrams-heap-iterative.js 3628800 real 0m0.855s user 0m0.000s sys 0m0.015s $ time node anagrams-megawac.js 3628800 real 0m2.286s user 0m0.000s sys 0m0.000s 

Comentarios

• Este es con mucho el ganador, calculando 3.628.800 resultados en ~5.000ms !
• ¡Genial! Debería calcular previamente los tamaños de las matrices que probablemente producirán resultados aún mayores (ya que los anagramas y el contador son matrices masivas). Creo que voy a tratar de tener que adoptar un enfoque distribuido para superar este 🙂
• Es ‘ interesante cómo se escala con entradas de diferentes tamaños jsperf.com/getanagramsc-r/2
• @megawac Me interesaría ver su enfoque después de utilizar los puntos fuertes de este enfoque.

Mientras trabajaba en una mejor solución, descubrí un gran uso para el nuevo JS Iterators & Generators , sobre los que he estado leyendo. Hoy pasé probablemente 6 horas jugando con esta solución, y fue vale la pena cada minuto. Tiene algunos errores de formato, pero Me voy a centrar completamente en el rendimiento y dejaré el formato a los otros revisores.

---

Ejecutar esto contra una palabra grande freirá tu máquina

Ok, así que tal vez eso también sea un poco lejos, pero En serio, esta es una función cara. No soy un gurú de las matemáticas, así que Hice esta pregunta en Math.SE .

La fórmula para calcular el número de combinaciones posibles es extremadamente empinada:

Piénselo así:

¿Cuántas opciones tiene para la primera letra? Cuatro: 4_ _ _ _.

¿Para el segundo? Tres: 4⋅3 _ _.

Continúe así y encontrará que hay 4⋅3⋅2⋅1 = 4! = 24 opciones en total. – MrRicci

Ejecutando su función contra la palabra «Enciclopedia» resultará en un bloqueo definitivo de la página si la ejecuta en el lado del cliente. Así que para solucionarlo, pensé un poco.

---

Ten paciencia conmigo: esto se vuelve cada vez más relevante a medida que lees.

Quería intentar generar palabras reales (divertirme con el codez)

Un anagrama es un tipo de juego de palabras, el resultado de reorganizar las letras de una palabra o frase para producir una nueva palabra o frase, usando todas las letras originales exactamente una vez – Wikipeda

Cuando pienso en un anagrama, pienso que el resultado son palabras o frases reales . Ahora, aunque el propósito de esta revisión de código no es cambiar la funcionalidad de su código, no pude evitar divertirme un poco con él. Así que decidí buscar una solución que me permitiera filtrar e imprimir cualquier anagrama de palabras reales del resultado.

Una vez que finalmente encontré una cadena de texto sin formato de ~ 130,000 palabras en inglés para usar como mi lista de palabras, luego necesitaba convertir esta lista en JS.Así que construí una función para cortar la cadena en cada espacio e imprimir la estructura de un objeto con propiedades clave, para poder probar muy rápidamente la validez de cualquier palabra a través de worldList["word"] -> returns true if word is valid.

Imprimir una lista de 130.000 palabras en el cuerpo del documento como una cadena JSON es, como su función, muy cara.

---

… Y la relevancia:

Entonces, aquí es donde su problema se encuentra con el que yo mismo inventé. ¿Cómo se procesa un ¿Un bucle muy caro sin bloquear una página web?

Al experimentar con las posibilidades, descubrí una manera de permitir que mi función manejar 130.000 palabras y su función para mantener una palabra de cualquier tamaño , al equilibrar la carga de trabajo a lo largo del tiempo.

Los bucles a veces son demasiado rápidos por su propio bien

Los bucles están hechos para ser lo más rápidos posible, lo cual es perfecto para la mayoría de las tareas para las que los utilizamos en las páginas web. Pero si les pedimos que manejen demasiado, el navegador no puede manejarlo.

Entonces necesitaba una solución que me permitiera distribuir la carga de trabajo a lo largo del tiempo, para permitir que la página manejara bucles costosos sin problemas.

Mi solución fue crear un bucle manual a través de una función que se llamaba a sí misma x veces, insertando un 1-2ms retraso entre iteraciones. Esto le dio a la página tiempo suficiente para manejar el ciclo , que, sin el retraso, procesó palabras increíblemente rápido hasta las C antes de estrellarse cada vez. Esto funcionó muy bien para generar mi estructura de lista de palabras JSON.

Pero un bucle retrasado fue extremadamente complicado de implementar en su función ya recursiva.

Me di cuenta entonces de que esta es la situación perfecta para utilizar una solución sobre la que leí recientemente para JavaScript …

---

Iteradores y generadores de JavaScript

Entonces, aquí vienen los iteradores de JavaScript & Generadores al rescate.

Ahora, esta revisión ya corre el riesgo de convertirse en un monstruo, así que en lugar de explicar los generadores, «voy a citar esta respuesta que pronto será popular «s one-liner:

TL; DR: la esencia de [usar un] generador es controlar la suspensión de la ejecución del código.

Y explique simplemente que los generadores son una forma mejorada de implementar iteradores.

Puede leer el resto por sí mismo en la respuesta allí. Si esa respuesta no es suficiente para usted, puede mejorar su comprensión a través de los siguientes recursos:

• Javascript «s Futuro: generadores

• Generadores: una mejor manera de crear iteradores

• Generadores – MDN

• ¿Cómo se llaman generadores?

Ahora, los generadores tienen un gran potencial en la tarea de evitar el infierno de las devoluciones de llamada, pero vamos a usarlos aquí no para formatear & estructura, sino para el rendimiento, que es (en mi opinión sesgada por el rendimiento) la razón más elegante para usarlos.

Todavía no estoy seguro de si los generadores son la mejor solución aquí, pero son la mejor idea que tengo, y esto es una excusa para probarlos.

---

Su código con generadores

Trabajando en esta solución todavía. Debería funcionar bien, simplemente no tengo tiempo para terminar todavía, y quería ofrecer el código mejorado más temprano que tarde. Publicaré esta solución pronto.

Actualización: unos días más tarde, no he terminado de aprender los generadores, hasta el punto de poder escribir esta función con ellos correctamente. Definitivamente lo publicaré aquí tan pronto como descubra su sintaxis un poco mejor.

---

Y finalmente, dado que los generadores son nuevos y aún no se admiten en todas partes … Una versión mejorada de su código sin ellos

Nota: Mis prácticas de formato son generalmente mi propia legibilidad preferencia en lugar de la mejor práctica. No se sienta obligado a formatear su código de esta manera.

/* Improved Real Time Anagram Engine */ // Without generators, it"s difficult to write this function // with the capability of processing a word of any length without // crashing the web browser, so this is written as the original, // with non-controlled execution speed. Long (9+ char) words may // crash browser. function generateAnagrams(word) { if (word.length < 2) { return [word]; } else { // By declaring all variables outside of the loop, // we improve efficiency, avoiding the needless // declarations each time. var anagrams = []; var before, focus, after; var shortWord, subAnagrams, newEntry; for (var i = 0; i < word.length; i++) { before = word.slice(0, i); focus = word[i]; after = word.slice(i + 1, word.length + 1); shortWord = before + after; subAnagrams = generateAnagrams(shortWord); for (var j = 0; j < subAnagrams.length; j++){ newEntry = focus + subAnagrams[j]; anagrams.push(newEntry); } } return anagrams; } } var result = generateAnagrams(word); 

Al declarar variables fuera de los bucles, ahorramos significativamente, ya que verás en los resultados. Además, creo que word.slice() funcionó un poco mejor que word.substr(). Entre las dos optimizaciones, este código realiza ser más que su código original.

---

Y por último, pero no menos importante, ¡el rendimiento resulta!

Código original : ¡Resultados actualizados! La página no se bloquea sin iniciar sesión.

• «código», 4 caracteres: 24 resultados , ~ 1ms
• «codificador», 5 caracteres: 120 resultados , ~ 1ms
• «codere», 6 caracteres: 720 resultados , ~ 6 ms
• «coderev», 7 caracteres: 5040 resultados , ~ 11ms
• «coderevi», 8 caracteres: 40,320 resultados , ~ 75 ms
• «coderevie», 9 caracteres: 362,880 resultados , página fallida
• «codereview», 10 caracteres: 3.628.800 resultados , error de página

Código mejorado : Resultados actualizados: la página no se bloquea sin iniciar sesión.

• » código «, 4 caracteres: 24 resultados , ~ 0.5ms
• » codificador «, 5 caracteres: 120 resultados , ~ 0.5ms
• «codere», 6 caracteres: 720 resultados , ~ 1.5ms
• «coderev», 7 caracteres: 5040 resultados , ~ 8ms
• » coderevi «, 8 caracteres: 40,320 resultados , ~ 53ms
• » coderevie «, 9 caracteres: 362,880 resultados , ~ 556ms
• «codereview», 10 caracteres: 3.628.800 resultados , ~ 12725ms

Tiempo real con generadores

(Código incompleto: los generadores están resultando un poco difíciles)

Usé console.time() para lograr mediciones precisas al milisegundo más cercano, completando 3-5 intentos cada uno y estimando un promedio general basado en el r resultados. Por supuesto, estos resultados variarán de una máquina a otra. Las comparaciones de tiempo son la clave para leer los puntos de referencia, no las velocidades.

---

Tl; Dr Summary, como se prometió

Los bucles son una herramienta extremadamente poderosa en la programación, pero no manejan bien un gran número de iteraciones costosas en el navegador web. Sin embargo, las costosas funciones de bucle como esta funcionan perfectamente si distribuye la carga de trabajo a lo largo del tiempo. Una forma interesante de hacerlo es usar JS Generators , un juguete nuevo disponible en las tiendas web hoy en día, pero no necesariamente en los mercados locales, así que utilícelo con cuidado hasta que JS 2.0 se implemente más ampliamente. Al utilizar la potencia de los generadores JS, podemos gestionar procesos costosos de larga ejecución sin ver ningún problema de rendimiento.

Comentarios

• ¿Alguna vez has descubierto los generadores?
• @megawac Pasé muchas horas en él, sin suficientes guías / información / tutoriales para descubrir realmente cómo hacerlo. I ‘ he estado gastando todo el tiempo que tengo libre cada día desde esta publicación para estudiarlos, pero … no ‘ aprendo rápidamente de la documentación en bruto. ¿Conoce algún buen recurso sobre generadores e iteradores?
• Suena como un buen hilo de stackoverflow @ jt0dd
• Escribí un solucionador para el periódico local ‘ s Jumble puzzle. Tenía una lista de 600.000 palabras de scrabble que preprocesé para ordenar las letras de cada palabra. Luego hice lo mismo con las letras de búsqueda y traté de encontrar palabras. Puede buscar todas las palabras entre 4 y 10 letras dadas 10 letras en milisegundos. Las letras ‘ throb ‘ ingresadas en cualquier orden dan como resultado ‘ bhort ‘ que enlaza directamente con ‘ throb ‘ y ‘ caldo ‘, no es necesario probar todas las combinaciones. Por ejemplo, si busca palabras de 4 letras con 5 letras, solo hay 4 combinaciones cuando las letras están ordenadas, 120 en caso contrario.
• @ jt0dd I ‘ estoy confundido sobre el uso de word.length + 1 cuando se usa slice. ¿Puede explicarnos?

Eché un vistazo al código de @ jt0dd y me pregunté cómo podría manejar algunos casos más. Te lo diré, agreguemos una capa de caché y calculemos previamente las longitudes de las matrices resultantes.

var generateAnagrams = (function() { // precomputed first 20 factorials var fact20 = [1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, 121645100408832000, 2432902008176640000]; // Substrings seen already which we can cache. Try and avoid stack overflow as much as possible var seenStrings = {}; function generateAnagrams(word) { var length = word.length; if (length < 2) { seenStrings[word] = word; return [word]; } var anagrams = Array(fact20[length - 1]); // Stuff we"ll need along the way var before, focus, after; var shortWord, subAnagrams, newEntry; var idx = 0, j, jlen; for (var i = 0; i < length; i++) { before = word.slice(0, i); focus = word[i]; after = word.slice(i + 1, word.length + 1); shortWord = before + after; subAnagrams = seenStrings[shortWord] || generateAnagrams(shortWord); for (j = 0, jlen = subAnagrams.length; j < jlen; j++) { newEntry = focus + subAnagrams[j]; anagrams[idx++] = newEntry; } } seenStrings[word] = anagrams; return anagrams; } return function anagrams(word) { var computed = generateAnagrams(word); // clear cache (going to consume a ton of memory) seenStrings = {}; return computed; }; })(); 

¡Hombre eso! ¡Qué feo! Espero que todo ese tiempo no haya sido en vano …

Hashs precalculados

• «código», 4 chars: 24 resultados , < = 1ms
• «codificador», 5 caracteres: 120 resultados , < = 1ms
• «codere», 6 caracteres: 720 resultados , < = 1ms
• «coderev», 7 caracteres: 5040 resultados , < = 3ms
• » coderevi «, 8 caracteres: 40,320 resultados , < = 18ms
• «coderevie», 9 caracteres: 362,880 resultados , 135ms
• «codereview», 10 caracteres: 3628,800 resultados , 2,1 s

Vaya, afrontamos el desafío. Veamos cuánto más podemos llegar. codereview es una palabra difícil, solo duplica los e. Intentemos algo más fácil para el siguiente Vamos. Intentemos "anagramarmy"

… … …

De acuerdo, mordí más de lo que mi navegador puede masticar al parecer, 40 millones de permutaciones de cadenas parecen estar más allá del límite 🙁

Notará que rediseñé el algoritmo para evitar el desbordamiento de la pila; las búsquedas deben realizarse fuera de la recursividad.

Podemos aumentar la posibilidad de que nuestro algoritmo no se bloquee haciéndolo asincrónico y haciendo todos los elementos 100,000 cada milisegundo para evitar que se detenga.

Comentarios

• ¡Genial! Esto es mucho mejor que la versión del generador en la que ‘ estoy trabajando. +1 ( Esta respuesta debería ser aceptada, ‘ va a ser mucho más eficiente que mi solución de generador.)
• Brillante … Simplemente genial. Realmente como esto. Cuando termine la solución del generador de armonía en tiempo real (o puede implementar la suya propia), no dude en tomarla y hacer lo mismo con ella. ‘ será más lento, pero devolverá los resultados en tiempo real y no tendrá fin a la extensión de una palabra que puede manejar.
• ahh, mjolka nos ganó ambos por far .
• Hola, ¿cómo ejecuto este código junto con html y css dentro de mi dominio? ‘ estoy usando este gratis: morsetovoynich.000webhostapp.com

Array.prototype.swap = function(i, j) { var el1 = this[i], el2 = this[j]; this[i] = el2; this[j] = el1; return this; }; Array.prototype.fastPush = function(element) { this[this.length] = element; }; String.prototype.fastSplit = function() { var array = []; for(var i = 0; i < this.length; i++) array.fastPush(this[i]); return array; }; Array.prototype.fastJoin = function() { var string = ""; for(var i = 0; i < this.length; i++) string += this[i]; return string; }; String.prototype.anagrams = function() { var i = 1, N = this.length, p = [], anagrams = [], k, word = this.fastSplit(); anagrams.fastPush(this.toString()); for(var j = 0; j < N; j++) p.fastPush(0); while(i < N) { if(p[i] < i) { k = 0; k = (i & 1 != 0) & p[i]; anagrams.fastPush(word.swap(k, i).fastJoin()); p[i]++; i = 1; } else { p[i] = 0; i++ } } return anagrams; }; console.log("asdasdfghj".anagrams()); 

(function() { var timeouts = []; var messageName = "zero-timeout-message"; // Like setTimeout, but only takes a function argument. There"s // no time argument (always zero) and no arguments (you have to // use a closure). function setZeroTimeout(fn) { timeouts.fastPush(fn); window.postMessage(messageName, "*"); } function handleMessage(event) { if (event.source == window && event.data == messageName) { event.stopPropagation(); if (timeouts.length > 0) { var fn = timeouts.shift(); fn(); } } } window.addEventListener("message", handleMessage, true); // Add the one thing we want added to the window object. window.setZeroTimeout = setZeroTimeout; })(); Array.prototype.swap = function(i, j) { var el1 = this[i], el2 = this[j]; this[i] = el2; this[j] = el1; return this; }; Array.prototype.fastPush = function(element) { this[this.length] = element; }; String.prototype.fastSplit = function() { var array = []; for(var i = 0; i < this.length; i++) array.fastPush(this[i]); return array; }; Array.prototype.fastJoin = function() { var string = ""; for(var i = 0; i < this.length; i++) string += this[i]; return string; }; var i = 1, p = [], N, k, chars, anagrams = [], r = 0; function anagramsGen(word) { N = word.length; chars = word.fastSplit(); anagrams.fastPush(word); for(var j = 0; j < N; j++) p.fastPush(0); noLimitWhile(); } function noLimitWhile() { if(i < N) { if(p[i] < i) { k = 0; k = (i & 1 != 0) & p[i]; anagrams.fastPush(chars.swap(k, i).fastJoin()); if(anagrams.length === 4e4) { if(r === 5) { console.clear(); r = 0; } r++; console.log(anagrams); anagrams = []; } p[i]++; i = 1; } else { p[i] = 0; i++ } setZeroTimeout(noLimitWhile); } else { console.log(anagrams); console.log("Finished"); } } anagramsGen("qwertyuiopas"); 

Otra variante más (escrita en C) usando un contador simple sobre el Power Set de todas las cadenas.

#include <string.h> #include <stdio.h> int main(int argc, char* argv[]) { if (argc < 2) return (1); char* arg = argv[1]; int n = 1 << strlen(arg); for (int i = 1; i < n; i++) { for (int j = 1, l = 0; j <= i; j <<= 1, l++) { if (i & j) printf("%c", arg[l]); } printf("\n"); } return (0); } 

Ejecutar con la impresión de todas las cadenas:

$ time anagrams codereview > log real 0m0.002s user 0m0.000s sys 0m0.000s 

Comentarios

• ¿Qué quieres decir con » impresión de todas las cadenas «? Su función solo genera partes de la palabra, por ejemplo, si ejecuta` anagramas abc` genera a,b,ab,c,ac,bc,abc

Matrices escritas para un mejor rendimiento.

Con el método de respuestas aceptado puede triplicar el rendimiento.

Ejecutar la respuesta ganadora en mi máquina dio como punto de referencia

Mean : 5,564,999µs ±182,246µs 11 samples 

Y al usar t arrays yped

Mean : 1,514,112µs ±72,000µs (*) 13 samples 

para un aumento de rendimiento de 3,68.

var knownPermutations = [0,0,0,24,120,720,5040,40320,362880,3628800]; function anagramer(input) { var counter, chars,length,i,index,tc,n,arraySize,anagrams; index = 0; length = input.length; arraySize = knownPermutations[length-1] * length; anagrams = new Uint8Array(arraySize); chars = new Uint8Array(length); counter = new Uint8Array(length); for( i = 0; i < length; i ++){ chars[i] = input.charCodeAt(i); } anagrams.set(chars) index += length; i = 0; while (i < length) { if (counter[i] < i) { tc = chars[i]; chars[i] = chars[n= (i%2?counter[i]:0)]; chars[n] = tc; counter[i]++; i = 0; anagrams.set(chars,index) index += length; } else { counter[i] = 0; i++; } } return anagrams; } 

Para mejorar un poco más puede predefinir la matriz de resultados para obtener

 Mean : 1,408,974µs ±25,173µs (*) 24 samples 

Para mejorarlo hasta 3.95 veces más rápido que la respuesta ganadora.