Вопрос по permutation, superset, regex – Regex для проверки неповторения набора символов

5

Предположим, у меня есть набор символов[ABC], Я ищу регулярное выражение, которое соответствовало бы любой перестановке надмножества, кроме пустого множества, т.е.

<code>ABC ACB BAC BCA CAB CBA
AB BC AC CB CA BA
A B C
</code>

Регулярное выражение должно (очевидно)not соответствовать пустой строке.

постскриптум Альтернативный способ выразить одну и ту же цель - «сопоставить любую непустую строку, содержащую каждый символ в наборе не более одного раза».

обновление: набор[ABC] Это всего лишь пример, потому что реальный набор также может быть больше. С этим вопросом я надеялся найти «общее» решение, а не конкретное для[ABC].

Ваш Ответ

8   ответов
6

что это можно решить с помощью регулярных выражений. Используйте это регулярное выражение:

/^([ABC])(?!\1)([ABC])?(?!\1|\2)[ABC]?$/

Дайте мне знать, если вам нужна онлайн-демонстрация по этому вопросу.

А вот и демо:regexr.com?30paf
Я также создал демо с большим количеством тестовых строк:rubular.com/r/TpkItUFW75
@anubhava И да, это работает! :-)
+1 отличная работа! это будет весело с большими наборами символов, хотя ...
@anubhava Я полагаю,(?!\1) означает & quot; смотри вперед и убедись, что совпадения №1 там нет & quot ;? Я не знал, что эта функция регулярных выражений существует (хотя, честно говоря, я пробовал ее как(?!$1) (почти как при замене). Я думаю, что сегодня узнал что-то новое ... :-)
3

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

\b(([ABC])(?!.*\2))+\b

\b необходимы для соответствия полных слов; если их пропустить, найдутся подслова, относящиеся к обязательному свойству. Чтобы сопоставить полную строку, вы, очевидно, сделаете:

^(([ABC])(?!.*\2))+$
Хорошо, я только что заметил это;really элегантный подход к теме (пробовал что-то подобное, но не смог заставить его работать ...: -S). Хорошая работа! :-)
1

Пытаться:

([ABC]?)(?!.*\1)([ABC]?)(?!.*\2)[ABC]?

Просто[ABC]? повторяется 3 раза с добавленной проверкой отрицательного прогнозного утверждения, которое не допускает дублирование символов.

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

See it work

Не работаетregexr.com?30pa3
0

Try this : (ОБНОВЛЕНО)

AC|BCA|CAB|CBA)(?![ABC])

Demo :

http://regexr.com?30pa6

Это будет соответствовать ААА, хотя (который из вопросаmay не быть в порядке)
Кроме того, я использовал группу из трех символов в качестве примера; фактический набор может быть больше. CAFxX
Все группы являются необязательными, поэтому они будут соответствовать пустой строке
@CAFxX - это может помочь, если вы упомянули об этом в вопросе
@ Джоанна обновил вопрос CAFxX
0

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

С математической точки зрения вы хотите определить всеpermutations of a set of elements without repetition.

Step 1 :

Найти все перестановки множества,with повторение (и хранить их, скажем, в массиве)

[ABC]([ABC]{1,2})?

Sidenote : let's say you have a set with n elements, all you have to do is :

[elements]([elements]{1,n-1})?

Step 2 :

Отфильтруйте все перестановки с дублирующимися элементами

Example code in PHP :

<?php

    function strToArray($str)
    {
        $i = 0;

        while (isset($str[$i]))
        {
            $result[$i] = $str[$i];
            $i++;
        }

        return $result;
    }

    function noDuplicates($str)
    {
        if (array_unique(strToArray($str))==strToArray($str)) return true;
        else return false;
    }

    $AAA = "AAA";
    $ABC = "ABC";

    if (noDuplicates($AAA)) echo "$AAA : ok"; else echo "$AAA : not ok\n";
    if (noDuplicates($ABC)) echo "$ABC : ok"; else echo "$ABC : not ok\n";

?>

Output :

AAA : not ok
ABC : ok
0

\b(?=[ABC]{1,3})([ABC]{1})(?:(?!\1)([ABC]{1})(?:(?!\1)(?!\2)[ABC]{1})?)?\b

Логика:

\b: look for a word boundary (?=[ABC]{1,3}): lookahead to see if there is a string of length = 3 with values of only A, B, C ([ABC]{1}): match the first character then optionally (?!\1)([ABC]{1}): check if the next character is not the same as previously matched - if it's not, match it and optionally (?!\1)(?!\2)[ABC]{1}: check if the next character is not the same as previously matched char 1 or 2 - if it's not, match the character

Я проверил это на этом входе, так что это кажется довольно надежным:

AABCC BBCC AB BC AC CB CA BA A B C ABC ACB BAC BCA CAB CBA AAA ABB AAA BBC А.А.

EDIT:

Поскольку вы упомянули, что набор символов может быть больше, я бы следовал совету PS в вашем вопросе и сделал бы это следующим образом:

introduce chars array which will hold each character in the allowed set (split the string into chars)

get an array of inputStrings (split the input string on whitespace or whatever else required)

for each string in inputStrings {

check if the string.length <= inputStrings.length tryMatch each character in the list against the current input and save the number of matches found in a matches list check if the matches list contains any entries and then if all entries == 1 or 0 }
1

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

что-то вроде:

def matches(s, characters):
    if len(s) != len(set(s)):
        return False # not unique sequence of characters
    return set(s).issubsetof(set(characters))
1
"A((B?C?)|(C?B?))|B((A?C?)|(C?A?))|C((A?B?)|(B?A?))"

и за каждым из них может следовать пара необязательных значений.

 A(B?C?) matches A, AB,AC and ABC
 A(C?B?) matches A, AC,AB and ACB 

но не ACAC, AA или ACC. Случаи с B или C в качестве первого символа эквивалентны.

Для более длинных строк это скоро станет ужасным. Лучший подход будет (псевдокод):

 string.sort().matches ("^A?B?C?$") && string.length > 0
@JanaWeschenfelder: я проверялecho ABA | grep -P '\b(([ABC])(?!.*\2))+\b' тоже успешно, но не знаю, с какой программой, с какими настройками она должна работать. :)
@JanaWeschenfelder: Спасибо, но я только что протестировал второе решение CAFxX, и оно работало и для меня, хотя и было намного меньше.
Ах, ладно ... Я неправильно понял ответ CAFxX. Я думал, что второе решение было просто альтернативой для первого решения. И я проверил там только первое решение.
Я знаю, команды echo, pipe и grep из Linux, он используется для применения регулярного выражения в консоли Unix или консоли Linux или Mac OS X и для его тестирования там. Он не будет работать под Windows, если вы не установите там что-то вроде Cygwin.
Похоже, единственно правильное решение для меня. На мой взгляд, это должно быть принятым решением. Большинство других решений (также принятых решений) по-прежнему допускают ABB, ACC, BAA, BBC, CCA и так далее.

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