Regular expression that matches anything in the powerset of a given set of characters

Question

I am writing a string pattern matching algorithm which I am planning to implement with regular expressions. I want the regex to be able to match any string in the powerset of a given list of characters.

I am expecting the regex to match in the following way:

Say we have a list s = ['a','c','t','a'].

Some strings that would match would be:

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

Similarly some strings that would not match would be:

aaa, tacca, iii, abcd, catk, ab

Keep in mind the number of occurrences of the character in the set is also considered.

This can also be expressed as a context-free grammar, if that helps in any way

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

Answer 1

It seems that if you search for the inverse this problem becomes very simple. Any input that contains any charaters other that a, c or t is not a match.

Then except for aa we should never see the same charater repeated. However aa can only be at the end of a string.

To solve the aa we can replace any aa at the end of the sting with a single a, as they are gramatically both the same.

We can then just search for aa, cc and tt and fail on any matches.

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))

In the above code I replace aa with A, but using a would also work.

Or in Ruby

 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

Answer 2

I would solve this without regex. It's easily done with a replace loop:

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)

prints:

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

---

As a function:

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

Of course this will also work with strings directly:

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

---

An optimized version that minimizes the number of .replace() calls:

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 3

One approach here would be to sort both the list of characters and the incoming substring. Then, build an in-order regex pattern consisting of the individual letters which should match.

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

To have a closer look at this solution, here is the list of characters as a string, after sorting, followed by the regex pattern being used:

aact
a.*t

Because the string to match against in now sorted, and the characters of the regex are in order, we can simply connect the letters by .*.