How to define a list of all binary strings that match specific RegExp?

Question

I have a regex that matches some binary strings. How to create a generator expression that defines a list of all strings that are accepted by this regex?

Please find the pseudocode.

pattern = re.compile("^(001|010|100){5}$") #accepts {001100001001001, 100100100001001,...} but not accepts {000000000000000,111111111111111,...}

def infinite_sequence():
    num = 000000000000000
    while True:
        yield num
        num += 1

good_binary_strings = [x for x in infinite_sequence() if re.match(pattern, x)]

I am interested in the most efficient code as possible. The real subset of strings is huge.

A naive approach: generate a list of binary strings and filter those which pass the test — Jan Stránský
– Jan Stránský, Commented Jul 17, 2020 at 12:06
I think this (translated from pseudocode to actual code) is pretty optimal.. For general case, you have to test all options.. — Jan Stránský
– Jan Stránský, Commented Jul 17, 2020 at 12:13

Jasmijn · Accepted Answer · 2020-07-17 14:35:59Z

1

The currently accepted answer by Jan Stránský generates 32767 different strings, which isn't too bad, but you can just straight up only generate the "good" strings, which is likely going to matter in your real dataset:

from itertools import product

good_binary_strings = [''.join(x) for x in product(['001', '010', '100'], repeat=5)]
print(len(good_binary_strings))

answered Jul 17, 2020 at 14:35

Jasmijn

10.7k2 gold badges33 silver badges49 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Jan Stránský · Accepted Answer · 2020-07-17 12:15:59Z

1

your modified code (assuming all length=15 binary strings):

import re
pattern = re.compile("^(001|010|100){5}$") #accepts {001100001001001, 100100100001001,...} but not accepts {000000000000000,111111111111111,...}

def infinite_sequence():
    num = 0
    while num <= 0b111111111111111:
        s = bin(num) # 0b10101
        s = s[2:] # 10101
        s = s.rjust(15,"0") # 000000000010101
        yield s
        num += 1

good_binary_strings = [x for x in infinite_sequence() if re.match(pattern, x)]
print(len(good_binary_strings))

answered Jul 17, 2020 at 12:15

Jan Stránský

1,6911 gold badge11 silver badges16 bronze badges

Collectives™ on Stack Overflow

How to define a list of all binary strings that match specific RegExp?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related