regex - 如何使用 Perl 从一组字母中生成单词列表？

Question

我正在寻找一个模块、正则表达式或任何其他可能适用于这个问题的东西。

如何以编程方式解析字符串并创建已知的英语 &|鉴于我有一个字典表，我可以根据它检查算法随机化的每个排列是否匹配？

给定一组字符:EBLAIDL KDIOIDSI ADHFWB
程序应返回:BLADE AID KID KIDS FIDDLE HOLA ETC....

我还希望能够定义最小和最大字长以及音节数

输入长度无所谓，只能是字母，标点也无所谓。

谢谢你的帮助

输入字符串中的 EDITLetters 可以重复使用。

例如，如果输入是:ABLED那么输出可能包含:BALL或 BLEED

Answer 1

您没有指定，所以我假设输入中的每个字母只能使用一次。

[你已经在输入中指定的字母可以多次使用，但我将把这篇文章留在这里，以防有人发现它有用。]

有效地做到这一点的关键是对单词中的字母进行排序。

abracadabra => AAAAABBCDRR
abroad      => AABDOR
drab        => ABDR

然后很明显，“单调”在“abracadabra”中。

abracadabra => AAAAABBCDRR
drab        => A    B  DR

而那个“国外”不是。

abracadabra => AAAAABBCD RR
abroad      => AA   B  DOR

我们将排序后的字母称为“签名”。如果您可以从“A”的签名中删除字母以获得“B”的签名，则单词“B”在单词“A”中。使用正则表达式模式很容易检查。

sig('drab') =~ /^A?A?A?A?A?B?B?C?D?R?R?\z/

或者，如果我们为了效率而消除不必要的回溯，我们会得到

sig('drab') =~ /^A?+A?+A?+A?+A?+B?+B?+C?+D?+R?+R?+\z/

现在我们知道了我们想要什么模式，这只是构建它的问题。

use strict;
use warnings;
use feature qw( say );

sub sig { join '', sort grep /^\pL\z/, split //, uc $_[0] }

my $key = shift(@ARGV);

my $pat = sig($key);
$pat =~ s/.\K/?+/sg;
my $re = qr/^(?:$pat)\z/s;

my $shortest = 9**9**9;
my $longest  = 0;
my $count    = 0;
while (my $word = <>) {
   chomp($word);
   next if !length($word);  # My dictionary starts with a blank line!! 
   next if sig($word) !~ /$re/;
   say $word;
   ++$count;
   $shortest = length($word) if length($word) < $shortest;
   $longest  = length($word) if length($word) > $longest;
}

say "Words:    $count";
if ($count) {
   say "Shortest: $shortest";
   say "Longest:  $longest";
}

例子:

$ perl script.pl EBLAIDL /usr/share/dict/words
A
Abe
Abel
Al
...
libel
lid
lie
lied

Words:    117
Shortest: 1
Longest:  6