Перестановки в регулярных выражениях;)

← →
Alexander Panov © (2005-05-24 15:05) [0]

Столкнулся с задачкой.
Есть набор символов, например - [abcd]

Необходимо проверить строку на совпадение из множества перестановок этих символов.

Что-то непонятно, есть ли такая возможность в рег. выражениях.

← →
Alx2 © (2005-05-24 15:11) [1]

>Alexander Panov © (24.05.05 15:05)
А зачем искать перестановки?
Проще проверить, что каждый символ строки встречается и в шаблоне и их количество совпадает.

← →
MOA © (2005-05-24 15:12) [2]

аааа - допустимо?

← →
Sergey13 © (2005-05-24 15:14) [3]

2[1] Alx2 © (24.05.05 15:11)
ИМХО совпадение количества в данном случае лишнее.

← →
Alx2 © (2005-05-24 15:15) [4]

>Alx2 © (24.05.05 15:11)

Э.. в обе стороны проверку надо. Строка-шаблон, Шаблон-строка

← →
Alx2 © (2005-05-24 15:16) [5]

>Sergey13 © (24.05.05 15:14)
Для перестановок не лишнее

← →
Sha © (2005-05-24 15:18) [6]

На порядок (или два) эффективнее свое написать.

← →
Alexander Panov © (2005-05-24 15:20) [7]

MOA © (24.05.05 15:12) [2]
аааа - допустимо?

Нет, недопустимо.

← →
Alexander Panov © (2005-05-24 15:28) [8]

Sha © (24.05.05 15:18) [6]
На порядок (или два) эффективнее свое написать.

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

Если это невозможно, тогда буду искать другие пути.

← →
Sha © (2005-05-24 15:30) [9]

> Alexander Panov © (24.05.05 15:28) [8]

Ну тогда перечисли все 24 слова.

← →
easy © (2005-05-24 15:34) [10]

"#([abcd]{4})#is"
?

← →
Игорь Шевченко © (2005-05-24 15:37) [11]

А может, ну их нафиг, эти регулярные выражения ? Может эта...нерегулярными обойтись ? А то одна неверно поставленная скобка и аллес гемахт.

← →
Ломброзо © (2005-05-24 15:38) [12]

m/[a-d][a-d][a-d][a-d]/gi

?

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

← →
Alexander Panov © (2005-05-24 15:41) [13]

Ломброзо © (24.05.05 15:38) [12]
m/[a-d][a-d][a-d][a-d]/gi
easy © (24.05.05 15:34) [10]
"#([abcd]{4})#is"

А без модификаторов?-0

Похоже, что невозможно это...
А жаль.-)

Игорь Шевченко © (24.05.05 15:37) [11]
А может, ну их нафиг, эти регулярные выражения ?

не-е-е... надо использовать достижения цивилизации;)

← →
Alexander Panov © (2005-05-24 15:41) [14]

Sha © (24.05.05 15:30) [9]
Ну тогда перечисли все 24 слова.

Видимо, да. Это вроде бы единственный выход.

← →
Ломброзо © (2005-05-24 15:42) [15]

Alexander Panov © (24.05.05 15:41)

Вообще, у easy правильно. А модификаторы - они чем мешают?

← →
Johnmen © (2005-05-24 15:42) [16]

>Alexander Panov ©

Мозги правишь Автомодератору ?
:)

← →
Alx2 © (2005-05-24 15:44) [17]

>Alexander Panov ©
>Johnmen © (24.05.05 15:42) [16]

А если все-таки "на матрешках" сначала тренироваться? :)

← →
easy © (2005-05-24 15:45) [18]

да и без модификаторов -

<?php $s="В разделе resourcestring файла Consts.pas перевести на русский язык те строки, которые вам необходимы. Можете перевести все, если хотите. Сохраните копию Consts.pas и пустое приложение вместе в отдельной папке. Обязательно подключите модуль Consts.pas(если вы его не подключили) к сохранённому приложению и сохраните приложение ещё раз. Обратите внимание: приложение должно использовать модуль Consts.pas, сохранённый вами вместе с самим приложением, а не из папки …\DelphiX\Source\Vcl. Чтобы убедиться в этом, закройте страницу Consts.pas, затем, удерживая Ctrl, кликните мышью в разделе модулей по слову Consts – должен открыться файл Consts.pas непосредственно из того места, где вы его сохранили. Запустите приложение. После того, как вы его запустили, в папке с приложением должен появиться файл Consts.dcu. В папке с сохранённым приложением у вас помимо прочих файлов типа Unit1.pas или project1.res должны быть следующие: Consts.pas и Consts.dcu. "; $reg="маи"; echo preg_replace( "#([$reg]{".strlen($reg)."})#" , "\\1", $s ); ?>

найдёт има,ами,мим
не знаю это то что надо или нет..

← →
Игорь Шевченко © (2005-05-24 15:45) [19]

Alexander Panov © (24.05.05 15:41) [13]

> не-е-е... надо использовать достижения цивилизации

Не советую. Слишком легко вместе с водой выплеснуть ребенка.

← →
Alexander Panov © (2005-05-24 15:45) [20]

Johnmen © (24.05.05 15:42) [16]

Мозги правишь Автомодератору ?

уг.

Ломброзо © (24.05.05 15:42) [15]
Вообще, у easy правильно. А модификаторы - они чем мешают?

А непонятно, что это за модификаторы.
В каждом движке свои модификаторы.

← →
False_Delirium © (2005-05-24 15:46) [21]

Одним регулярным выражением ?

Одним - наврятли. Если есть, то крайне неэффективно.

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

← →
Alexander Panov © (2005-05-24 15:47) [22]

easy © (24.05.05 15:45) [18]

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

← →
Alexander Panov © (2005-05-24 15:48) [23]

False_Delirium © (24.05.05 15:46) [21]
Одним регулярным выражением ?

Необязательно одним, можно и последовательными проверками, но только не общего количества перестановок-)

← →
Ломброзо © (2005-05-24 15:49) [24]

Alexander Panov © (24.05.05 15:45)

А непонятно, что это за модификаторы.

Я знаком с перловым, Java и микрософтовским. Основных модификатора три, и они присутствуют во всех этих движках: глобальный поиск (g), игнорирование регистра (i) и трактование переноса строки как пробельного символа (s)

← →
Alexander Panov © (2005-05-24 15:51) [25]

Ломброзо © (24.05.05 15:49) [24]

Модификаторы

Модификаторы служат для изменения режимов работы TRegExpr.

Вы можете изменять модификаторы несколькими способами.

Любой модификатор может меняться с помощью специальной конструкции (?...) внутри регулярного выражения.

Также, Вы можете присвоить значение соответствующему свойству экземпляра объекта TRegExpr (например, ModifierX для изменения модификатора /x, или ModifierStr для изменения сразу нескольких модификаторов). Значения по умолчанию для новых экземпляров объектов TRegExpr определены в глобальных константах, например RegExprModifierX определяет значение по умолчанию для ModifierX.

i

Регистро-независимый режим (по умолчанию использует выбранный в ОС язык по умолчанию), (см. также InvertCase)

m

Воспринимать входной текст как многострочный, при этом метасимволы "^"" и "$"" будут совпадать не только в начале и конце текста в целом, но и в начале и в конце всех имеющихся в тексте строк (см. также Разделители строк)

s

Воспринимать входной текст как одну строку. При этом метасимвол "."" совпадает с любым символом, если же этот модификатор выключен, то он не совпадает с разделителями строк (см.также Разделители строк).

g

Не стандартный модификатор. Выключая его Вы переключаете все повторители в "не жадный" режим (по умолчанию этот модификатор включен). Т.е. если его отключить, то все "+" работают как "+?", "*" как "*?" и т.д.

x

Позволяет форматировать шаблон чтобы обеспечить более легкую читаемость (см. описание ниже).

r

Не стандартный модификатор. Если включен, то диапазоны вида а-я включают также букву "ё", А-Я включают "Ё", а а-Я включает вообще все русские буквы.

← →
easy © (2005-05-24 16:12) [26]

var abcd,expr:string; begin abcd := "abcd"; expr:="(?i)(["+abcd+"]{"+inttostr(length(abcd))+"})"; caption:=booltostr(ExecRegExpr(expr,Memo1.Text),true); end;

← →
Alexander Panov © (2005-05-24 16:17) [27]

easy © (24.05.05 16:12) [26]

(?i)([abcd]{4})

Срабатывает на строку "aabb"

← →
MOA © (2005-05-24 16:37) [28]

Я тут подумал - а ведь требование "перестановки из Н неповторяющихся символов", похоже - не есть регулярная, она даже и не контекстно-свободная грамматика...

← →
Sha © (2005-05-24 16:52) [29]

На Паскале примерно так:
procedure TForm1.Button1Click(Sender: TObject); const pattern: string="abcd"; var s: string; mem: array[0..255] of integer; cur, last, dist, len, ch, count: integer; begin; len:=Length(pattern); FillChar(mem[0],256*4,255); for cur:=1 to len do mem[ord(pattern[cur])]:=0; s:="aaabcabd"; count:=0; for cur:=1 to length(s) do begin; ch:=ord(s[cur]); last:=mem[ch]; if last<0 then count:=0 else begin; mem[ch]:=cur; dist:=cur-last; if dist<len then count:=dist else begin; inc(count); if count>=len then break; end; end; end; Caption:=IntToStr(count); end;

← →
Igorek © (2005-05-24 17:02) [30]

Alexander Panov © (24.05.05 15:05)
Если для проверки полагаться целиком на регулярное выражение (правильная строка - это грамматически правильная строка), то оно будет достаточно громоздким. Напр. для "abc" - "a(bc|cb)|b(ac|ca)|c(ab|ba)". Для генерации сией трахомудии можно использовать такой код:
//написал по быстрому, жутко неефективный, прошу не пинать

function MakeRegExpr(const str: string): string; function _Exclude(const str: string; X: Integer): string; var I: Integer; begin result := ""; for I := 1 to Length(str) do if I <> X then result := result + str[I]; end; var I, L: Integer; begin L := Length(str); if L = 1 then result := str[1] else begin result := ""; for I := 1 to L do begin if I > 1 then result := result + "|"; result := result + str[I]; if L > 2 then result := result + "("; result := result + MakeRegExpr(_Exclude(str, I)); if L > 2 then result := result + ")"; end; end; end;

← →
Alexander Panov © (2005-05-24 17:04) [31]

да, похоже, что проще реализовать обработку флажка, и функцию проверки на ссоответствие перестановке.

← →
Igorek © (2005-05-24 17:04) [32]

Удалено модератором

← →
Ломброзо © (2005-05-24 17:04) [33]

Igorek © (24.05.05 17:02)
Alexander Panov © (24.05.05 15:05)

IncDay №2

← →
Alexander Panov © (2005-05-24 17:06) [34]

Sha © (24.05.05 16:52) [29]
Igorek © (24.05.05 17:02) [30]

Спасибо.

← →
DiamondShark © (2005-05-24 17:11) [35]

Удалено модератором
Примечание: Самый верный способ испортить отношения - это начать их выяснять. /Николай Векшин/ (AutoModerator)

← →
MOA © (2005-05-24 17:12) [36]

Кстати, если писать программульку и важно быстродействие - можно завести массив с буквами (в пределе - 256) и счётчиком. После разбора - пробежаться по массиву счётччиков, если везде 1 - совпадение, иначе нет. Должно получиться очень просто (тупой цикл по Н эл-там строки + цикл по счётчикам) и очень быстро ;).

← →
Alexander Panov © (2005-05-24 17:13) [37]

DiamondShark © (24.05.05 17:11) [35]

Соревнования не будет. Будет R/O.
Чик. Все просто.

← →
Alexander Panov © (2005-05-24 17:13) [38]

Alexander Panov © (24.05.05 17:13) [37]
Будет R/O.

Причем навечно.

Робот на РО не обидится ;)

Кстати, до анализа бреда я еще доберусь. Не до него пока.

>Alexander Panov © (24.05.05 17:18)

>Кстати, до анализа бреда я еще доберусь. Не до него пока.

Кстати, в начале октября в МГУ проходит
всероссийская научно-техническая конференция "Методы и средства обработки информации “МСО-2005”. Участвовать будешь, если получится?

Сама затея изначально дурацкая.

DiamondShark © (24.05.05 17:21) [44]
Сама затея изначально дурацкая.

Ничего... Что-то еще будет, когда автомодератор R/O раздавать начнет.

>если буквы в строке встречаются, но не подряд?
Тогда да, необходим сброс счётчиков. Если мы пытаемся найти подстроку.

> Что-то еще будет, когда автомодератор R/O раздавать начнет.

Я могу побыть Нострадамусом и предсказать: на сайте останется только автомодератор и вопрошающие.

Удалено модератором
Примечание: Жизнь дается только раз, но и совесть тоже. /Александр Солженицын/ (AutoModerator)

Ладно, спасибо всем.
Наверное, придется на паскале отдельную функцию использовать для такой задачи.

> Игорь Шевченко © (24.05.05 17:25) [49]
>
> > Что-то еще будет, когда автомодератор R/O раздавать начнет.
>
>
> Я могу побыть Нострадамусом и предсказать: на сайте останется
> только автомодератор и вопрошающие.

Думаю, вопрошающие тоже разбегуться...правда, не сразу -)

>на сайте останется только автомодератор и вопрошающие

Верно замечено: именно "автомодератор и вопрошающие". А модераторов не будет, поскольку они все будут в R/O.
=)

VMcL © (24.05.05 21:17) [53]
Верно замечено: именно "автомодератор и вопрошающие". А модераторов не будет, поскольку они все будут в R/O.

Модераторов исключим из списка.

Точно.
Останется один Панов, беседующий с собственным роботом.

Перестановки в регулярных выражениях;) Найти похожие ветки