Gere todas as combinações possíveis de letras em uma palavra

 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("") 

Vou jogar meu chapéu no ringue com a versão iterativa do método do heap de geração de permutações. Demorei um pouco para acertar, pois minha fonte de referência tem um erro de digitação no 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; } 

Com alguns tempos de amostra para contar os 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 

Comentários

• Este é de longe o vencedor, calculando 3.628.800 resultados em ~5,000ms!
• Legal! Você deve pré-calcular os tamanhos de array provavelmente produzirá resultados ainda maiores (pois anagramas e contador são arrays enormes). Acho que vou tentar ter uma abordagem distribuída para vencer este 🙂
• É ‘ interessante como isso se dimensiona com entradas de tamanhos diferentes jsperf.com/getanagramsc-r/2
• @megawac Eu estaria interessado em ver sua abordagem depois de utilizar os pontos fortes desta abordagem.

Enquanto trabalhava em uma solução melhor, descobri um ótimo uso para o novo JS Iterators & Generators , sobre os quais tenho lido. Passei provavelmente 6 horas hoje tentando resolver esta solução, e foi vale cada minuto. Você tem alguns erros de formatação, mas vou focar totalmente no desempenho e deixar a formatação para os outros revisores.

---

Executar isso contra uma palavra grande irá fritar sua máquina

Ok, então talvez isso “esteja indo um pouco também longe mas sério, esta é uma função cara. Não sou um guru da matemática, então Fiz esta pergunta no Math.SE .

A fórmula para calcular o número de combinações possíveis é extremamente íngreme:

Pense assim:

Quantas opções você tem para a primeira letra? Quatro: 4_ _ _ _.

Para o segundo? Três: 4⋅3 _ _.

Continue assim e você descobrirá que há 4⋅3⋅2⋅1 = 4! = 24 opções no total. – MrRicci

Executando sua função em relação à palavra A “Enciclopédia” resultará em uma falha definitiva da página se você executá-la no lado do cliente. Então, para corrigir isso, pensei um pouco.

---

Tenha paciência – isso fica cada vez mais relevante conforme você lê.

Eu queria tentar gerar palavras reais (me divertindo com o código)

Um anagrama é um tipo de jogo de palavras, o resultado da reorganização das letras de uma palavra ou frase para produzir uma nova palavra ou frase, usando todas as letras originais exatamente uma vez – Wikipeda

Quando penso em um anagrama, penso que o resultado são palavras ou frases reais . Agora, embora o objetivo desta revisão de código não seja alterar a funcionalidade do seu código, não pude deixar de querer me divertir um pouco com ele. Portanto, decidi procurar uma solução que me permitisse filtrar e imprimir quaisquer anagramas de palavras reais do resultado.

Assim que finalmente localizei uma string de texto simples de ~ 130.000 palavras em inglês para usar como minha lista de palavras, então precisei converter esta lista em JS.Portanto, criei uma função para fatiar a string em cada espaço e imprimir a estrutura de um objeto com propriedades codificadas, de modo que pudesse testar rapidamente a validade de qualquer palavra por meio de worldList["word"] -> returns true if word is valid.

Imprimir uma lista de 130.000 palavras no corpo do documento como uma string JSON é, como sua função, muito caro.

---

… E a relevância:

Então, aqui “é onde seu problema encontra aquele que eu inventei para mim. Como você processa loop muito caro sem travar uma página da web?

Ao experimentar as possibilidades, eu realmente descobri uma maneira de permitir que minha função lidar com 130.000 palavras e sua função para sustentar uma palavra de qualquer tamanho , equilibrando a carga de trabalho ao longo do tempo.

Os loops às vezes são muito rápidos para seu próprio bem

Os loops são feitos para ser o mais rápido possível, o que é perfeito para a maioria das tarefas para as quais os usamos em páginas da web. Mas se pedirmos a eles para lidar com muito, o navegador não pode lidar com isso.

Portanto, eu precisava de uma solução que me permitisse distribuir a carga de trabalho ao longo do tempo, a fim de permitir que a página manuseie loops caros sem problemas.

Minha solução foi construir um loop manual por meio de uma função que se autodenomina x vezes, inserindo um 1-2ms atraso entre iterações. Isso deu à página tempo suficiente para lidar com o loop , que, sem demora, processou palavras Insanamente rápido até os C “s antes de bater todas as vezes. Isso funcionou muito bem para gerar minha estrutura de lista de palavras JSON.

Mas um loop atrasado era extremamente complicado de implementar em sua função já recursiva.

Percebi então que esta é a situação perfeita para utilizar uma solução que li recentemente para JavaScript …

---

Iteradores e geradores de JavaScript

Então, aqui estão os Iteradores de JavaScript & Geradores para o resgate.

Agora, esta revisão já é um risco de se tornar um monstro, então, em vez de explicar Geradores, vou citar esta resposta logo se tornará popular “s one-liner:

TL; DR: a essência de [usar um] gerador é controlar a suspensão da execução do código.

E explique simplesmente que os geradores estão em uma maneira aprimorada de implementar iteradores.

Você pode ler o resto por si mesmo na resposta aqui. Se essa resposta não funcionar para você, você pode melhorar sua compreensão por meio dos seguintes recursos:

• Javascript “s Futuro: Geradores

• Geradores: a melhor maneira de construir Iteradores

• Geradores – MDN

• O que essa coisa é chamada de geradores?

Agora, os geradores têm um grande potencial na tarefa de evitar o inferno do retorno de chamada, mas vamos use-os aqui não para formatar & estrutura, mas para desempenho, que é (na minha opinião tendenciosa por desempenho) a razão mais elegante para usá-los.

Não tenho certeza ainda se os geradores são a melhor solução aqui, mas eles são a melhor ideia que eu tenho, e esta é uma desculpa para experimentá-los.

---

Seu código com geradores

Trabalhando esta solução ainda. Deve funcionar muito bem, só não tenho tempo para terminar ainda e gostaria de oferecer o código aprimorado mais cedo ou mais tarde. Vou postar esta solução em breve.

Atualização: alguns dias mais tarde, ainda não terminei de aprender geradores, a ponto de ser capaz de escrever essa função com eles corretamente. Definitivamente irei postá-la aqui assim que descobrir sua sintaxe um pouco melhor.

---

E, finalmente, uma vez que os geradores são novos e não são suportados em todos os lugares ainda .. Uma versão aprimorada do seu código sem eles

Observação: minhas práticas de formatação geralmente são fáceis de ler preferência em vez de prática recomendada. Não se sinta obrigado a formatar seu código dessa maneira.

/* 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); 

Ao declarar variáveis fora dos loops, economizamos significativamente, pois você verá nos resultados. Além disso, acredito que word.slice() teve um desempenho ligeiramente melhor do que word.substr(). entre as duas otimizações, este código executa ser superior ao seu código original.

---

E por último, mas não menos importante, os resultados de desempenho!

Código original : Resultados atualizados! A página não trava sem fazer login.

• “code”, 4 caracteres: 24 resultados , ~ 1ms
• “coder”, 5 caracteres: 120 resultados , ~ 1ms
• “codere”, 6 caracteres: 720 resultados , ~ 6ms
• “coderev”, 7 caracteres: 5040 resultados , ~ 11ms
• “coderevi”, 8 caracteres: 40.320 resultados , ~ 75ms
• “coderevie”, 9 caracteres: 362.880 resultados , falha de página
• “codereview”, 10 caracteres: 3.628.800 resultados , falha de página

Código aprimorado : Resultados atualizados – a página não trava sem registrar.

• ” código “, 4 caracteres: 24 resultados , ~ 0,5 ms
• ” coder “, 5 caracteres: 120 resultados , ~ 0,5 ms
• “codere”, 6 caracteres: 720 resultados , ~ 1,5 ms
• “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

Tempo real com geradores

(Código incompleto – os geradores estão se mostrando um pouco difíceis)

Usei console.time() para obter medições precisas até o milissegundo mais próximo, completando 3-5 tentativas cada e estimando uma média geral com base em r resultados. É claro que esses resultados variam de máquina para máquina. As comparações de tempo são a chave para a leitura de benchmarks, não as velocidades.

---

Resumo do Tl; Dr, conforme prometido

Os loops são extremamente poderosos ferramenta na programação, mas eles não lidam bem com números monstruosos de iterações caras no navegador da web. Funções de loop caras como esta funcionam perfeitamente, no entanto, se você distribuir a carga de trabalho ao longo do tempo. Uma maneira interessante de fazer isso é usar Geradores JS , um novo brinquedo disponível nas lojas da web hoje, mas não necessariamente nos mercados locais, então use com cuidado até que JS 2.0 seja mais amplamente implementado! Utilizando o poder dos geradores JS, podemos gerenciar processos caros de longa duração sem ver quaisquer problemas de desempenho.

Comentários

• Será que você já descobriu geradores?
• @megawac Passei muitas horas nisso, sem guias / informações / tutoriais suficientes para realmente descobrir como fazê-lo. I ‘ tenho gasto o máximo de tempo que tenho livre a cada dia desde esta postagem para estudá-los, mas … Eu não ‘ não aprendo rapidamente com a documentação bruta. Você conhece algum bom recurso sobre geradores e iteradores?
• Parece um bom thread stackoverflow @ jt0dd
• Escrevi um solucionador para o jornal local ‘ s Jumble puzzle. Eu tinha uma lista de 600.000 palavras scrabble que pré-processei para classificar as letras de cada palavra. Em seguida, fiz o mesmo para as letras de pesquisa e tentei encontrar palavras. Ele pode procurar todas as palavras entre 4 e 10 letras, com 10 letras em milissegundos. As letras ‘ throb ‘ inseridas em qualquer ordem resultam em ‘ bhort ‘ que se vincula diretamente a ‘ throb ‘ e ‘ caldo ‘, não há necessidade de tentar todas as combinações. Por exemplo, se estiver procurando por palavras de 4 letras com 5 letras, há apenas 4 combinações quando as letras são classificadas, 120 se não.
• @ jt0dd I ‘ m confused sobre o uso de word.length + 1 ao usar o slice. Você pode explicar?

Eu dei uma olhada no código de @ jt0dd “e me perguntei como nós poderia lidar com mais alguns casos. Vou lhe dizer, vamos adicionar uma camada de cache e pré-calcular os comprimentos dos arrays 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; }; })(); 

Cara que ” é feio! Espero que todo esse tempo não tenha sido em vão …

Hashs pré-calculados

• “code”, 4 chars: 24 resultados , < = 1ms
• “coder”, 5 caracteres: 120 resultados , < = 1 ms
• “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: 3.628.800 resultados , 2.1 s

Uau, vencemos o desafio. Vamos ver o quanto mais podemos ir. codereview é uma palavra dura apenas duplicar e caracteres. Vamos tentar algo mais fácil para o próximo vá. Vamos tentar "anagramarmy"

… … …

Ok, mordi mais do que meu navegador pode mastigar ao que parece, 40 milhões de permutações de strings parecem estar além do limite 🙁

Você notará que redesenhei o algoritmo para evitar o estouro de pilha – as pesquisas devem ser feitas fora da recursão.

Podemos aumentar a chance de nosso algoritmo não travar, tornando-o assíncrono e fazendo todos os 100,000 elementos a cada milissegundo para evitar a parada.

Comentários

• Incrível! É muito melhor do que a versão do gerador em que ‘ estou trabalhando. +1 ( Essa resposta deve ser aceita, ‘ vai ser muito mais eficiente do que minha solução de gerador.)
• Brilhante … Simplesmente brilhante. Realmente como isso. Quando eu terminar a solução do gerador de harmonia em tempo real (ou você pode implementar a sua própria), fique à vontade para pegá-la e fazer o mesmo com ela. Ele ‘ será mais lento, mas retornará resultados em tempo real e não terá limite para o tamanho de uma palavra que ele pode suportar.
• ahh, mjolka nos venceu ambos por far .
• Olá, como executo este código juntamente com html e css dentro do meu domínio? Eu ‘ estou usando este grátis: morsetovoynich.000webhostapp.com

Fiz dois scripts:

1. O primeiro é rápido, mas não pode “segurar muito;
2. O segundo é lento, mas pode mostrar resultados ilimitados.

Ambos usam o protótipo que fiz: fastPush, fastSplit e fastJoin; que são mais rápidos do que o método padrão de divisão e junção. Ambos também use bit a bit para verificar se é ímpar ou par, porque sei que o mod é a operação mais lenta possível em um computador.

O primeiro script bate o resultado mais rápido dos outros por mais de 750ms (em média) em um desafio de permutação de 10 caracteres .

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()); 

De qualquer forma, este primeiro programa tem um limite e quebra a página se você tentar mais de 10 caracteres.

O segundo programa (o abaixo) usa uma função de auto-invocação e faz login nos blocos do console de elementos 4e4, ele limpa o array de anagramas cada vez que produz um bloco e também limpa co nsole.log a cada 5 chunks (o suficiente para permitir que você veja essas combinações). Para auto-invocar a função, o programa usa setZeroTimeout ( blog de David Baron ) em vez de setTimeout porque setTimeout é muito mais lento.

(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"); 

Mais uma variante (escrita i C) usando um contador simples sobre Conjunto avançado de todas as strings.

#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); } 

Executar com impressão de todas as strings:

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

Comentários

• O que você quer dizer com ” impressão de todas as strings “? Sua função apenas exibe partes da palavra, por exemplo, se run` anagrams abc` outputs a,b,ab,c,ac,bc,abc

Arrays digitados para melhor desempenho.

Usando o método de respostas aceitas, você pode triplicar o desempenho.

Executar a resposta vencedora em minha máquina deu benchmarked

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

E ao usar t arrays yped

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

para aumento de desempenho 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 melhorar um pouco mais você pode predefinir a matriz de resultados para obter

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

Para melhorá-la em até 3,95 vezes mais rápido que a resposta vencedora.