Единственный способ представить, как это сработает, - это проанализировать все возможные комбинации букв и сравнить их со словарем. Самый быстрый способ сравнить их со словарем - это превратить этот словарь в хеш. Таким образом, вы можете быстро узнать, было ли это слово верным.
Я набираю в своем словаре нижний регистр всех букв в словарном слове, а затем удаляю все не-буквенные символы, чтобы быть в безопасности. Для значения я буду хранить фактическое слово словаря. Например:
cant => "can't",
google => "Google",
Таким образом, я могу отобразить правильно написанное слово.
Я нашел Math :: Combinatorics , который выглядел довольно неплохо, но не совсем так, как я надеялся. Вы даете ему список букв, и он будет возвращать все комбинации этих букв в указанном вами количестве. Таким образом, я думал, что все, что мне нужно было сделать, это преобразовать буквы в список отдельных букв и просто просмотреть все возможные комбинации!
Нет ... Это дает мне все неупорядоченные комбинации. Затем мне нужно было с каждой комбинацией перечислить все возможные сочетания этих букв. Мля! Ptooy! Yech!
Итак, печально известный цикл в цикле. На самом деле, три петли.
* Внешний цикл просто отсчитывает все числа комбинаций от 1 до количества букв в слове.
* Следующая находит все неупорядоченные комбинации каждой из этих групп букв.
* Наконец, последний берет все неупорядоченные комбинации и возвращает список перестановок из этих комбинаций.
Теперь я наконец могу взять эти сочетания букв и сравнить их со своим словарем слов. Удивительно, но программа работала намного быстрее, чем я ожидал, учитывая, что ей пришлось превратить словарь из 235 886 слов в хеш, а затем выполнить цикл по трем циклам, чтобы найти все перестановки всех комбинаций из любого возможного количества букв. Вся программа запустилась менее чем за две секунды.
#! /usr/bin/env perl
#
use strict;
use warnings;
use feature qw(say);
use autodie;
use Data::Dumper;
use Math::Combinatorics;
use constant {
LETTERS => "EBLAIDL",
DICTIONARY => "/usr/share/dict/words",
};
#
# Create Dictionary Hash
#
open my $dict_fh, "<", DICTIONARY;
my %dictionary;
foreach my $word (<$dict_fh>) {
chomp $word;
(my $key = $word) =~ s/[^[:alpha:]]//;
$dictionary{lc $key} = $word;
}
#
# Now take the letters and create a Perl list of them.
#
my @letter_list = split // => LETTERS;
my %valid_word_hash;
#
# Outer Loop: This is a range from one letter combinations to the
# maximum letters combination
#
foreach my $num_of_letters (1..scalar @letter_list) {
#
# Now we generate a reference to a list of lists of all letter
# combinations of $num_of_letters long. From there, we need to
# take the Permutations of all those letters.
#
foreach my $letter_list_ref (combine($num_of_letters, @letter_list)) {
my @letter_list = @{$letter_list_ref};
# For each combination of letters $num_of_letters long,
# we now generate a permeation of all of those letter
# combinations.
#
foreach my $word_letters_ref (permute(@letter_list)) {
my $word = join "" => @{$word_letters_ref};
#
# This $word is just a possible candidate for a word.
# We now have to compare it to the words in the dictionary
# to verify it's a word
#
$word = lc $word;
if (exists $dictionary{$word}) {
my $dictionary_word = $dictionary{$word};
$valid_word_hash{$word} = $dictionary_word;
}
}
}
}
#
# I got lazy here... Just dumping out the list of actual words.
# You need to go through this list to find your longest and
# shortest words. Number of syllables? That's trickier, you could
# see if you can divide on CVC and CVVC divides where C = consonant
# and V = vowel.
#
say join "\n", sort keys %valid_word_hash;
Запуск этой программы произвел:
$ ./test.pl | column
a al balei bile del i lai
ab alb bali bill delia iba laid
abdiel albe ball billa dell ibad lea
abe albi balled billed della id lead
abed ale balli blad di ida leal
abel alible be blade dial ide led
abide all bea blae dib idea leda
abie alle bead d die ideal lei
able allie beal da dieb idle leila
ad allied bed dab dill ie lelia
ade b beid dae e ila li
adib ba bel dail ea ill liable
adiel bad bela dal ed l libel
ae bade beld dale el la lid
ai bae belial dali elb lab lida
aid bail bell dalle eld label lide
aide bal bella de eli labile lie
aiel bald bid deal elia lad lied
ail baldie bide deb ell lade lila
aile bale bield debi ella ladle lile