Регулярное выражение, которое соответствует чему-либо в powerset данного набора символов

Question

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

Я ожидаю, что регулярное выражение совпадет следующим образом:

Скажем, у нас есть список s = ['a','c','t','a'].

Некоторые строки, которые будут соответствовать, будут:

cat, act, tac, at, aa, t, acta, taca, a

Аналогично, некоторые строки, которые не будут соответствовать, будут:

aaa, tacca, iii, abcd, catk, ab

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

Это также можно выразить как контекстную грамматику, если это поможет каким-либо образом

S → A | T | C
A → aT | aC | a | aa | ɛ
T → tA | tC | t | ɛ
C → cA | cT | c | ɛ

Answer 1

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

s = ['a','c','t','a']
test_strings = ['cat', 'act', 'tac', 'at', 'aa', 't', 'acta', 'taca', 'a',
                'aaa', 'tacca', 'iii', 'abcd', 'catk', 'ab']

for t in test_strings:
    temp = t
    for c in s:
        temp = temp.replace(c, '', 1)

    if temp == '':
        print('match: ' + t)
    else:
        print('no match: ' + t)

печатает:

match: cat
match: act
match: tac
match: at
match: aa
match: t
match: acta
match: taca
match: a
no match: aaa
no match: tacca
no match: iii
no match: abcd
no match: catk
no match: ab

---

Как функция:

def is_in_powerset(characters, target):
    for c in characters:
        target = target.replace(c, '', 1)
    return target == ''

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

print(is_in_powerset('acta', 'taa'))

---

Оптимизированная версия, которая минимизирует количество вызовов .replace():

from itertools import groupby

def get_powerset_tester(characters):
    char_groups = [(c, sum(1 for _ in g)) for c, g in groupby(sorted(characters))]
    def tester(target):
        for c, num in char_groups:
            target = target.replace(c, '', num)
        return target == ''
    return tester

tester = get_powerset_tester('acta')
for t in test_strings:
    if tester(t):
        print('match: ' + t)
    else:
        print('no match: ' + t)

Answer 2

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

s = ['a','c','t','a']
s.sort()
str = ''.join(s)
substring = "at"
substring = '.*'.join(sorted(substring))
print(substring)
if re.match(substring, str):
    print("yes")

a.*t
yes

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

aact
a.*t

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

Answer 3

Кажется, что если вы ищете обратное, эта проблема становится очень простой. Любые входные данные, содержащие любые символы, отличные от a, c или t, не совпадают.

Тогда, кроме aa, мы никогда не увидим повторение одного и того же персонажа. Однако aa может быть только в конце строки .

Чтобы решить aa, мы можем заменить любой aa в конце укуса одним a, так как они грамматически оба одинаковы.

Затем мы можем просто найти aa, cc и tt и потерпеть неудачу при любых совпадениях.

import re

test_strings = {
   'cat' : True,
   'act' : True,
   'tac' : True,
   'at' : True,
   'aa' : True,
   't' : True,
   'acta' : True,
   'taca' : True,
   'a' : True,
   'aaa' : False,
   'ataa' : True,
   'aataa' : False,
   'tacca' : False,
   'iii' : False,
   'abcd' : False,
   'catk' : False,
   'ab' : False,
   'catcat' : True,
   'cat' * 40000 : True,
   'actact' : True,
}

for t, v in test_strings.items():
    if not re.search("^[atc]*$", t):
        continue;

    temp = re.sub("aa$", "A", t)
    if re.search("^aa|aA|cc|tt", temp):
        print('no match(%r): %s' % (v, t))
    else:
        print('match(%r): %s' % (v, t))

В приведенном выше коде я заменяю aa на A, но использование a также будет работать.

или в рубине

 test_strings = {
   'cat' => true,
   'act' => true,
   'tac' => true,
   'at' => true,
   'aa' => true,
   't' => true,
   'acta' => true,
   'taca' => true,
   'a' => true,
   'aaa' => false,
   'ataa' => true,
   'aataa' => false,
   'tacca' => false,
   'iii' => false,
   'abcd' => false,
   'catk' => false,
   'ab' => false,
   'catcat' => true,
   'cat' * 40000 => true,
   'actact' => true,
}

test_strings.each do |t, v|
    temp = t.dup
    if !temp.match(/^[atc]*$/)
      puts('No match: ' + t + ' ' + temp)
      next;
    end
    temp.sub!(/aa$/, 'A');
    if temp.match(/aA|aa|tt|cc/)
       puts('no match: ' + t[0..80])
       puts "Wrong" if v
    else
       puts('match: ' + t[0..80])
       puts "Wrong" unless v
    end
end