Вопрос по perl, regex – Используя регулярные выражения, чтобы найти слово с пятью буквами abcde, каждая буква появляется ровно один раз, в любом порядке, без перерывов между ними.

14

Например, словоdebacle будет работать из-заdebac, ноseabed не сработает, потому что: 1. в любой 5-символьной последовательности нет c, и 2. буква e появляется дважды. В качестве другого примера,feedback будет работать из-заedbac, И помните, решение должно быть сделано с использованием только регулярных выражений.

Стратегия, которую я пытался реализовать, заключалась в следующем: сопоставьте первую букву, если она внутри [a-e], и запомните ее. Затем найдите следующую букву в [a-e], но не первую букву. И так далее. Я не был уверен, какой был синтаксис (или даже если какой-то синтаксис существовал), поэтому мой код не работал:

open(DICT, "dictionary.txt");
@words = <DICT>;

foreach my $word(@words){

if ($word =~ /([a-e])([a-e^\1])([a-e^\1^\2])([a-e^\1^\2^\3])([a-e^\1^\2^\3^\4])/
){
    print $word;
}
}

Я также думал об использовании (? = Regex) и \ G, но я не был уверен, как это сработает.

Ваш Ответ

3   ответа
7

Ваше решение умно, но, к сожалению,[a-e^...] не работает, как вы нашли. Я не верю, что есть способ смешивать обычные и отрицательные классы персонажей. Я могу придумать обходной путь, используя взгляды, хотя:

    /(([a-e])(?!\2)([a-e])(?!\2)(?!\3)([a-e])(?!\2)(?!\3)(?!\4])([a-e])(?!\2)(?!\3)(?!\4])(?!\5)([a-e]))/

Смотрите это здесь:http://rubular.com/r/6pFrJe78b6.

UPDATE: Моб отмечает в комментариях ниже, что чередование может быть использовано для уплотнения выше:

    /(([a-e])(?!\2)([a-e])(?!\2|\3)([a-e])(?!\2|\3|\4])([a-e])(?!\2|\3|\4|\5)([a-e]))/

Новая демка:http://rubular.com/r/UUS7mrz6Ze.

Но вы можете использовать чередование:...(?!\2|\3|\4|\5)
Обратите внимание, что вы не можете иметь обратные ссылки внутри классов символов. Отсюда необходимость множественных обратных ссылок вместо чего-то вроде(?![\2\3\4\5]), Кроме того, мне пришлось начинать считать с 2, а не с 1, потому что я хотел включить «общий». группа захвата для рублевой демонстрации.
15
/
   (?= .{0,4}a )
   (?= .{0,4}b )
   (?= .{0,4}c )
   (?= .{0,4}d )
   (?= .{0,4}e )
/xs

Это, вероятно, приводит к более быстрому сопоставлению, чтобы генерировать шаблон из всех комбинаций.

use Algorithm::Loops qw( NextPermute );
my @pats;
my @chars = 'a'..'e';
do { push @pats, quotemeta join '', @chars; } while NextPermute(@chars);
my $re = join '|', @pats;

ABCDE | abced | abdce | abdec | abecd | abedc | acbde | acbed | acdbe | acdeb | acebd | acedb | adbce | adbec | adcbe | adceb | adebc | adecb | aebcd | aebdc | aecbd | aecdb | aedbc | aedcb | bacde | baced | badce | badec | baecd | baedc | bcade | bcaed | bcdae | bcdea | bcead | bceda | bdace | bdaec | bdcae | bdcea | bdeac | bdeca | beacd | beadc | becad | becda | bedac | bedca | cabde | cabed | cadbe | cadeb | caebd | caedb | cbade | cbaed | cbdae | cbdea | cbead | cbeda | cdabe | cdaeb | cdbae | cdbea | cdeab | cdeba | ceabd | ceadb | cebad | cebda | ЦБДО | cedba | dabce | dabec | dacbe | daceb | daebc | daecb | dbace | dbaec | dbcae | dbcea | dbeac | dbeca | dcabe | dcaeb | dcbae | dcbea | dceab | dceba | deabc | deacb | debac | debca | decab | decba | eabcd | eabdc | eacbd | eacdb | eadbc | eadcb | ebacd | ebadc | ebcad | ebcda | ebdac | ebdca | ecabd | ecadb | ecbad | ecbda | ecdab | ecdba | edabc | edacb | edbac | edbca | edcab | edcba

(Это будет оптимизировано в три в Perl 5.10+. До 5.10 используйте Regexp :: List.)

Альтернативное решение также работает, если вы хотите найти материал с дубликатом (например, abcdd вместо abcde)
Добавлено альтернативное решение.
Это было опрятное решение, +1
+1 - мне нравится это лучше, чем мое собственное решение. Для объяснения другим сторонам прогнозирования гарантируют, что: в следующих 5 буквах имеется по меньшей мере один 'a', по меньшей мере один 'b', по меньшей мере один 'c', по меньшей мере один 'd'; и, по меньшей мере, один 'е'. Учитывая, что имеется только пять "слотов", " гарантируется, что каждый из них будет отображаться ровно один раз.
6
#! perl -lw
for (qw(debacle seabed feedback)) {
    print if /([a-e])(?!\1)
        ([a-e])(?!\1)(?!\2)
        ([a-e])(?!\1)(?!\2)(?!\3)
        ([a-e])(?!\1)(?!\2)(?!\3)(?!\4)
        ([a-e])/x;
}

Похожие вопросы