Estou tentando escrever um script de shell para gerar todas as palavras possíveis no idioma inglês com menos de 20 caracteres. Eu duvido que exista uma maneira realmente eficiente de fazer isso, além da força bruta. É claro que isso vai gerar muitos jargões, mas através do conjunto completo, se o escopo for computável em um período decente de tempo, espero explorar aspectos da linguagem humana.
Além disso, se alguém souber como calcular ou me dizer qual é o espaço que eu gostaria de saber. Eu acho que isso é combinatória básica ou permutações, mas eu não sei qual é qual. 26 cartas. 20 ou 25 de comprimento. Tenho certeza de que 25 fornece complexidade suficiente para chegar a algumas boas palavras, mas isso aumentará drasticamente a computação. No set, sem dúvida, seria aaaaaaadfsf e também bungologia.
Na verdade, existe um arquivo chamado /usr/share/words , que contém todas as palavras em inglês.
Eu provavelmente usaria esse arquivo para encontrar todas as palavras em inglês e para obter as palavras até um determinado tamanho, você pode fazer como,
awk 'length <=20' /usr/share/words | wc -l
Eu recebo 479396 palavras dentro desse arquivo.
Se você quiser palavras com 20 caracteres, então com 26 letras, há
26^20 = 19928148895209409152340197376
possibilidades. Os computadores são rápidos hoje em dia, mas são rápidos o suficiente? Boa sorte;)
Como você está procurando palavras que sejam inferiores a 20 characters , isso inclui palavras com 1, 2, 3 .. or 19 characters de comprimento (não tenho certeza se há uma palavra no idioma inglês com 19 caracteres). O número total de possibilidades é então 26 19 + 26 18 + 26 17 .. + 26 1 .
A maneira da força bruta de abordar esse problema é criar uma lista que inclua todos os 26 alfabetos do idioma inglês. Em seguida, dentro de um loop for i = 0; i < 20; i++ , você cria todas as palavras possíveis de comprimento i usando os 26 caracteres da matriz de alfabeto. A recursão é sua amiga aqui. Depois de ter uma palavra de comprimento i , você pode passá-la por meio de filtering rules a ser usado para definir palavras no idioma inglês, por exemplo nenhuma palavra pode existir sem uma vogal como mencionado por slm.
Nota: Escrever o chamado filtering rules não é uma tarefa trivial. Por exemplo, é bastante fácil verificar se a palavra contém aieou , mas passar essa verificação não significa que você encontrou uma palavra ... ainda há um longo caminho a percorrer.
Por quanto tempo esse método de força bruta será usado?
Jimmij postou que 26^20 = 19928148895209409152340197376 ~ 2e28 . Agora, digamos que seu computador tenha um quad core 1.5 GHz processor e seu programa possa explorar cada núcleo 100% . Isso lhe dá 1.5e9 x 4 = 6e9 ciclos em um segundo. Cada permutação em si levará multiple CPU cycles , já que tem que considerar 26 characters para cada permutação, etc. Esse número, no entanto, é insignificante quando comparado ao # of permutations , então digamos que cada permutação leva 6 instructions (e cada instrução leva 1 CPU cycle ) para simplificar as contas. Finalmente, você recebe (6 instructions/permutation x 2e28 permutations)/(6e9 instructions/second) = (2e19 seconds) ~ 6.35e11 years .