Регулярные выражения. Поиск слов по набору букв

#регулярные_выражения #поиск

Помогите составить регулярное выражение для поиска слов только по определённому набору
букв. Т.е. Есть слово "зажигалка" в результате в искомых словах могут использоваться
только буквы из этого слова и в том же количестве.

Нужно найти все слова, состоящие из этих букв. Т.е. "глаз", "газ", "галка" и т.д.
В общем, как в игре "Слова из слова"
    

Ответы

Ответ 1

Если речь о перестановке букв, то:

^(?=.*з)(?=.*а.*а.*а)(?=.*ж)(?=.*и)(?=.*г)(?=.*л)(?=.*к)[зажиглк]{9}$


Если речь просто о подмножестве, то так:

^(?!.*з.*з)(?!.*а.*а.*а.*а)(?!.*ж.*ж)(?!.*и.*и)(?!.*г.*г)(?!.*л.*л)(?!.*к.*к)[зажиглк]+$


Ответ 2

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

если условие про количество опустить и если слова идут по одному в строке, то, например, так:

$ echo -e 'глаз\nгаз\nмозг\nгалка' | grep '^[зажигалка]\+$'
глаз
газ
галка




под дополнительным кодом я имею ввиду:


преобразование искомой строки в отсортированный список букв с квантификатором количества
для букв, встречающихся более одного раза. например: зажигалка преобразовать в ^а{1,3}?г?ж?з?и?к?л?$
(или чуть по-другому, только с квантификаторами количества и без квантификатора ?:
^а{0,3}г{0,1}ж{0,1}з{0,1}и{0,1}к{0,1}л{0,1}$)
преобразование слова на входе в отсортированный список букв. например: мозг → гзмо,
глаз → агзл, заза → аазз.


если такие преобразования выполнить, то движок, понимающий bre (basic regular expressions),
вполне справится:

$ echo -e 'гзмо\nагзл\nаазз' | grep '^а\{1,3\}\?г\?ж\?з\?и\?к\?л\?$'
агзл




пример выполнения описанных преобразований средствами posix-утилит:


преобразование исходного слова в регулярное выражение bre:

$ echo 'зажигалка' | sed 's/./&\n/g;s/.$//' | sort | uniq -c | \
 sed -r 's/\s*([0-9]+)\s*(.*)/\2\\{0,\1\\}/;1s/^/^/;$s/$/$/' | \
 sed ':a;N;s/\n//;ta'
^а\{0,3\}г\{0,1\}ж\{0,1\}з\{0,1\}и\{0,1\}к\{0,1\}л\{0,1\}$

сортировка букв:

$ echo 'глаз' | sed 's/./&\n/g;s/.$//' | sort | sed ':a;N;s/\n//;ta'
агзл





обновление: в своём ответе Qwertiy продемонстрировал, что без второго из описанных
мною преобразований можно обойтись, если использовать стандарт pcre (perl compatible
regular expressions), в котором есть функция предпросмотра (look-ahead).

первое преобразование в таком случае может быть сделано средствами posix-утилит,
например, так:

$ w='зажигалка'; echo $w | sed 's/./&\n/g;s/.$//' | sort | uniq -c | \
 sed -r 's/^\s*([0-9]+)\s*(.)$/echo \\(?!\\(.*\2\\)\\{$((\1+1))\\}\\)/e;1s/^/^/;$s/$/['$w']+$/' | \
 sed ':a;N;s/\n//;ta'
^(?!(.*а){4})(?!(.*г){2})(?!(.*ж){2})(?!(.*з){2})(?!(.*и){2})(?!(.*к){2})(?!(.*л){2})[зажигалка]+$


полученное регулярное выражение работает корректно:

$ echo -e 'мозг\nглаз\nзаза' | grep -P '^(?!(.*а){4})(?!(.*г){2})(?!(.*ж){2})(?!(.*з){2})(?!(.*и){2})(?!(.*к){2})(?!(.*л){2})[зажигалка]+$'
глаз