Регулярное выражение, соответствующее любому подмножеству данного набора?

Question

Можно ли написать регулярное выражение, которое будет соответствовать любому подмножеству данного набора символовa1 ... an?Т.е. он должен соответствовать любой строке, где любой из этих символов встречается не более одного раза, других символов нет, и относительный порядок символов не имеет значения.

Некоторые подходы, возникающие одновременно:1. [a1,...,an]* или (a1|a2|...|an)* - допускается многократное присутствие символов2. (a1?a2?...an?) - нет многократного присутствия, но важен относительный порядок - это соответствует любой подпоследовательности , но не подмножеству .3. ($|a1|...|an|a1a2|a2a1|...|a1...an|...|an...a1), т.е. записывать все возможные подпоследовательности (просто жестко закодировать все соответствующие строки :)), конечно, это неприемлемо.

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

Любая помощь будет оценена.Заранее спасибо.

Answer 1

Это на самом деле не подходит для тега language-agnostic, но ...

^(?:(?!\1)a1()|(?!\2)a2()|...|(?!\n)an())*$

см. Демонстрацию на ideone.com

При первом сопоставлении элемента он «проверяется» группой захвата, следующей за ним. Поскольку группа теперь участвовала в совпадении, отрицательный прогноз ее соответствующей обратной ссылки (например, (?!\1)) никогда не будет совпадать, даже если группа захватила только пустую строку. Это недокументированная функция, которая, тем не менее, поддерживается во многих разновидностях, включая Java, .NET, Perl, Python и Ruby.

Это решение также требует поддержки прямых ссылок (то есть ссылки на заданную группу захвата (\1), которая появляется в регулярном выражении перед самой группой). Похоже, это немного менее широко поддерживается, чем трюк с пустыми группами.

Answer 2

Не могу придумать, как это сделать с одним регулярным выражением, но это один из способов сделать это с n регулярным выражением: (Я буду использовать 1 2 ... m n и т. Д. для ваших a с)

^[23..n]*1?[23..n]*$
^[13..n]*2?[13..n]*$
...
^[12..m]*n?[12..m]*$

Если все вышеперечисленное совпадает, ваша строка является строгим подмножеством 12..mn.

Как это работает: каждая строка требует, чтобы строка состояла из точно из:

• любое количество символов, взятых из набора, кроме a particular one
• возможно a particular one
• любое количество символов, взятых из набора, кроме a particular one

Если это проходит, когда каждый элемент по очереди рассматривается как a particular one, мы знаем:

• в строке нет ничего, кроме разрешенных элементов
• существует не более одного из разрешенных элементов

по мере необходимости.

---

для полноты я должен сказать, что я сделал бы это, только если бы мне было приказано "использовать регулярные выражения"; если нет, я бы отслеживал, какие элементы были видны, и перебирал символы строки, делая очевидные вещи.

Answer 3

Не уверен, что вы можете получить расширенное регулярное выражение для этого, но это довольно легко сделать простым обходом вашей строки.

Вы используете хеш (или массив, или что-то еще) для хранения, если какой-либо из ваших разрешенных символов уже был замечен или отсутствует в строке. Затем вы просто перебираете элементы вашей строки. Если вы столкнетесь с элементом, которого нет в вашем разрешенном наборе, вы спасаетесь. Если это разрешено, но вы уже видели это, вы тоже спасаетесь.

В псевдокоде:

foreach char a in {a1, ..., an}
   hit[a1] = false

foreach char c in string
   if c not in {a1, ..., an} => fail
   if hit[c] => fail
   hit[c] = true

Answer 4

Аналогично Алану Муру, использует только \ 1 и не относится к группе захвата до того, как ее увидят:

#!/usr/bin/perl
my $re = qr/^(?:([abc])(?!.*\1))*$/;
foreach (qw(ba pabc abac a cc cba abcd abbbbc), '') {
    print "'$_' ", ($_ =~ $re) ? "matches" : "does not match", " \$re \n";
}

Мы сопоставляем любое количество блоков (внешний (? :)), где каждый блок должен состоять из «точно одного символа из нашего предпочтительного набора, за которым не следует строка, содержащая этот символ».

Если строка может содержать символы новой строки или другие забавные вещи, возможно, придется поиграть с некоторыми флагами, чтобы сделать ^, $ и. ведите себя так, как задумано, но все зависит от конкретного вкуса RE.

Просто для глупости можно использовать положительное упреждающее утверждение для эффективного И двух регулярных выражений, поэтому мы можем проверить любую перестановку abc, утверждая, что приведенные выше совпадения, за которыми следует обычная проверка на ', состоят из N символов и состоит из следующих символов:

my $re2 = qr/^(?=$re)[abc]{3}$/;
foreach (qw(ba pabc abac a cc abcd abbbbc abc acb bac bca cab cba), '') {
    print "'$_' ", ($_ =~ $re2) ? "matches" : "does not match", " \$re2 \n";
}