Generating sequential alphanumeric values that match a certain pattern

Question

I'm working on generating large volumes of test data for some performance testing. Part of this is going to involve generating a lot of values that represent an "MBI", which is a certain kind of alpha-numeric identifier.

This identifier has the following rules:

• Is alpha-numeric (uppercase only letters)
• Excludes letters that are commonly confused for numbers or other letters (SLOIBZ)
• Is 11 digits long
• Has specific rules on which values can go in which digit
  • The first digit can be a number 1-9
  • The second, fifth, eighth, and ninth digits can be any upper case letter besides SLOIBZ; I don't actually validate the upper-case requirement, and I just call mbi.upper() as needed.
  • The fourth, seventh, tenth, and eleventh digits can be any number 0-9
  • The remaining digits (third and sixth) can be any of the valid letters or numbers (including 0)

The following function validates that an MBI is valid (you can assume this is correct for your own review)

Assuming that the numbers are "before" the letters, the "first" MBI is then "1A00A00AA00". My task is to generate a whole bunch of valid and unique MBIs by "incrementing" them. For example, I want to be able to do this:

for _, mbi in zip(range(count_mbis_to_generate), mbi_generator("1A00A00AA99")):
    print(mbi)

This should print count_mbis_to_generate distinct MBIs, starting with "1A00A00AA99" (assuming there are that many distinct MBIs that are greater than or equal to "1A00A00AA99". If I wanted 10000 of them, then the last one should be "1A00A00GA98".

---

To accomplish this, I started by writing a function to validate that a given MBI matches the expected format:

import re

def validate_mbi(mbi):
    flags = re.IGNORECASE ^ re.VERBOSE
    pattern = re.compile(
        r"""
        [1-9]                      # No leading zeros
        [ac-hjkmnp-rt-z]           # No letters that can be confused for numbers or each other
        [ac-hjkmnp-rt-z\d]         # Letter or number
        \d                         # Any number
        [ac-hjkmnp-rt-z]           
        [ac-hjkmnp-rt-z\d]         
        \d                         
        [ac-hjkmnp-rt-z]{2}        # Then two letters
        \d{2}                      # Then two numbers
        """,
        flags=flags,
    )
    return mbi and len(mbi) == 11 and pattern.match(mbi)

I then created a generator that will start spitting out MBIs:

def mbi_generator(start=None):
    if not start:
        start = "1A00A00AA00"

    while validate_mbi(start):
        yield start

        start = increment_mbi(start)

Now I actually had to do some thinking. To do this arithmatic by hand, I came up with the following algorithm:

1. Starting with the final digit (e.g. mbi[10]), attempt to increment it by 1 (following all normal rules)
2. If that results in a "carrying" operation, then set this digit to the minimum allowed value for this digit, and move on to the next digit
3. Repeat until I get to the first digit (e.g. mbi[0]).
4. If the first digit is the largest allowed value as well (9), then we cannot increment this MBI, so just return None

To accomplish this, I created dictionaries that I'm calling "pseudo-linked lists" (they are nowhere close to a true linked list, but it was the name that popped in my head when I made it). They would look like this:

• If my current value is 'A', then the next value is 'B' and we don't have to carry.
• If my current value is 'Z', then that is the largest possible value, so the "next" value is either 0 or 'A', depending on digit, and we do have to carry.

This would end up looking like this kind of dictionary (for the 0-9 digits):

{'0': ('1', False),
 '1': ('2', False),
 '2': ('3', False),
 '3': ('4', False),
 '4': ('5', False),
 '5': ('6', False),
 '6': ('7', False),
 '7': ('8', False),
 '8': ('9', False),
 '9': ('0', True)}

The key is the current value, and then the value's first index is the "next" value, and the second index is the "carry" flag. Note that the values are strings, not numbers, because we're always operating on strings and its easier to store it this way than do conversions all over the place.

The function to spit out one of these dictionaries is like so:

def build_pseudo_linked_list(value_list):
    end_point = len(value_list) - 1

    return {
        current_value: (value_list[0] # Get the first value
                        if i == end_point # If we're at the end of the list
                        else value_list[i + 1], # Otherwise get the next value
                        i == end_point) # Whether or not we were at the end of the list
        for i, current_value in enumerate(value_list)
    }

From there, I just need to build up the different kinds of dictionaries, and then use them to increment the MBI.

def increment_mbi(mbi):
    # Get the list of possible values for each digit
    string_list = [char for char in string.ascii_uppercase if char not in "SLOIBZ"] # exclude easily confused letters
    digit_list = [str(i) for i in range(0, 10)] # any digit
    partial_digit_list = [val for val in digit_list if val != "0"] # Any non-zero digit
    combined_list = digit_list + string_list # any value from any list above

    # The values a given digit can have as a pseudo-linked list
    # current_value : (next_value, should_advance_digit)
    first_digit_range = build_pseudo_linked_list(partial_digit_list)
    letter_range = build_pseudo_linked_list(string_list)
    full_digit_range = build_pseudo_linked_list(digit_list)
    combined_range = build_pseudo_linked_list(combined_list)

    # Each digit's ranges
    ranges = [
        first_digit_range,
        letter_range,
        combined_range,
        full_digit_range,
        letter_range,
        combined_range,
        full_digit_range,
        letter_range,
        letter_range,
        full_digit_range,
        full_digit_range,
    ]
    index = 10  # Start from the back
    mbi = mbi.upper() # If they gave us lower-case values, just roll with it

    # Starting from the back, try to increment digits until we don't have to carry
    for i in range(index, 0, -1):
        next_value, should_advance = ranges[i][mbi[i]]

        # If we get to the front and we need to reset, then we can't go any further
        if i == 0 and should_advance:
            return None

        # Otherwise, slide our value in
        mbi = mbi[:i] + next_value + mbi[i + 1 :]
        # If we need to advance to the next digit then we continue, otherwise return our current state
        if not should_advance:
            return mbi

At this point, the logic was pretty straightforward, and mostly just requires building up our dictionaries and lists.

I'm looking for a review on a few things:

1. Does this make sense? I need to add docstrings that explain all of this still, but hopefully the reasoning makes sense
2. Would making these classes actually help at all? I played around with it, but it didn't really seem to be any clearer than before
3. Are there any obvious ways to make this faster? This is working well enough to generate test data, which can be a "run it over the weekend on rare occasions" kind of thing, but I'd love for it to be faster.

Bonus points if you come up with a really clever itertools implementation; I played with it for a while but it eventually got a little too obtuse for me

Answer 1

This is a fun problem. I've taken the liberty of writing an alternate implementation, which I will describe below. Note that I've not focused too much on performance at all, only on simplicity and good structure.

Suggested

from typing import Iterable

N = 11


class MBI:
    letters = tuple('ACDEFGHJKMNPQRTUVWXYZ')
    numbers = tuple(str(i) for i in range(10))
    digits = (
        numbers[1:],
        letters,
        numbers + letters,
        numbers,
        letters,
        numbers + letters,
        numbers,
        letters,
        letters,
        numbers,
        numbers,
    )
    assert len(digits) == N
    sizes = tuple(len(d) for d in digits)

    def __init__(self, indices: Iterable[int] = (0,)*N):
        indices = list(indices)
        assert len(indices) == N
        self.indices = indices

    def copy(self):
        return MBI(self.indices)

    @classmethod
    def parse(cls, as_str: str):
        assert len(as_str) == N
        return MBI((
            digs.index(s)
            for digs, s in zip(cls.digits, as_str)
        ))

    @classmethod
    def is_valid(cls, as_str: str) -> bool:
        try:
            cls.parse(as_str)
            return True
        except Exception as e:
            return False

    def __str__(self):
        return ''.join(digs[i] for digs, i in zip(self.digits, self.indices))

    def add(self, addend=1):
        for pos in range(N-1, -1, -1):
            carry, digit = divmod(self.indices[pos] + addend, self.sizes[pos])
            self.indices[pos] = digit
            if carry:
                if pos == 0:
                    raise ValueError()
                addend = carry
            else:
                break


def increasing_same(mbi: MBI, n: int, addend: int = 1) -> Iterable[MBI]:
    for _ in range(n):
        yield mbi
        mbi.add(addend)


def increasing_copy(mbi: MBI, n: int, addend: int = 1) -> Iterable[MBI]:
    for _ in range(n):
        yield mbi
        mbi = mbi.copy()
        mbi.add(addend)


def test():
    assert MBI.is_valid('1A00A00GA98')
    assert not MBI.is_valid('2')
    assert not MBI.is_valid('00000000000')
    assert MBI.parse('1A00A00GA98').indices == [
        0, 0, 0, 0, 0, 0, 0, 5, 0, 9, 8
    ]
    assert MBI.parse('1A00A00AA00').indices == [0]*N
    assert str(MBI()) == '1A00A00AA00'


def demo():
    for mbi in increasing_same(MBI.parse('4M44M44MN98'), 6):
        print(mbi)
    print()

    for mbi in increasing_same(MBI.parse('8ZZ9ZZ9ZZ95'), 10, 2):
        print(mbi)
    print()


if __name__ == '__main__':
    test()
    demo()

Rationale

This is class-based. You asked

Would making these classes actually help at all?

The answer is, in general, yes. Modelling a class like I've shown allows you to encapsulate parsing, formatting, validation and increment logic all in one tidy package. The class instance is mutable, so you can choose whether to iterate-and-mutate or iterate-and-copy.

As to your validation strategy: You do not need regexes; just attempt to parse and catch a failure. Parsing into a machine-usable sequence of integers can serve both purposes: preparation for processing, as well as validation that the thing is processible at all.

Another sensible modification is generalization of the addend in your incrementing logic. You can add by any number, not just incrementing by one, and the change is easy enough that it's better to make a generic function that can add anything instead of something that can only increment.

Does this make sense?

It's more complicated than it needs to be, and it isn't really tested. The suggested implementation includes some rudimentary tests that give you more confidence that this thing is doing what it should.

Answer 2

Explicit is better than implicit.

Simple is better than complex.

Readability counts.

The easiest way to make it faster would be to simply convert it into code:

def generate_mbis() -> Iterator[str]:
    """ Generate MBIs, starting with 1A00A00AA00.

        An MBI is a string with the following rules:

        [1-9]                      # No leading zeros
        [ac-hjkmnp-rt-z]           # No letters that can be confused for numbers or each other
        [ac-hjkmnp-rt-z\d]         # Letter or number
        \d                         # Any number
        [ac-hjkmnp-rt-z]           
        [ac-hjkmnp-rt-z\d]         
        \d                         
        [ac-hjkmnp-rt-z]{2}        # Then two letters
        \d{2}                      # Then two numbers
    """
    LETTERS = "acdefghjkmnpqrtuvwxyz".upper()
    D0_9 = "0123456789"

    # Using 2-space indents because so many
    for p0 in range(1, 9):
      for p1 in LETTERS:
        for p2 in LETTERS + D0_9:
          for p3 in D0_9:
            for p4 in LETTERS: 
              for p5 in LETTERS + D0_9:
                for p6 in D0_9:
                  for p7 in LETTERS:
                    for p8 in LETTERS:
                      for p9 in D0_9:
                        for p10 in D0_9:
                          yield p1+p2+p3+p4+p5+p6+p7+p8+p9+p10

You could probably improve speed by caching the partial sums in the inner loops. You might see some gain by using purely numeric indexing, using range instead of for ... in .... (I don't know this, I just suspect it.)

Implementing a start-string would be straightforward, but would require an if/else at each level. You might make a helper function for that. (Edit: this turns out to be wrong. See below for an example of resuming.)

Edit:

It's worth noting that yes, you could use itertools.product to get the same effect:

for tpl in itertools.product(range(1, 9),
                             LETTERS,
                             LETTERS + D0_9,
                             D0_9, 
                             LETTERS,
                             LETTERS + D0_9,
                             D0_9,
                             LETTERS,
                             LETTERS,
                             D0_9,
                             D0_9):
    yield ''.join(tpl)

But you won't have any opportunity to tweak the performance. It's worth trying, but I expect you'll be able to use a bytearray or partial sum or something to get better speed than you can from this approach.

Edit:

There was some question in the comments about (re)starting from an arbitrary location and how it would affect performance. Here's a simple 3-digit demo program to show how it could be done:

import string

def gen_999(start: str = None):
    if start is None:
        start = '000'

    # Figure out the starting values
    s0, s1, s2 = ('000' + str(start))[-3:]
    digits = string.digits

    d0 = digits[digits.index(s0):]
    d1 = digits[digits.index(s1):]
    d2 = digits[digits.index(s2):]

    for p0 in d0:
        for p1 in d1:
            for p2 in d2:
                yield p0 + p1 + p2
            d2 = digits
        d1 = digits
    d0 = digits  # Included only for symmetry.

def main():
    for i, mbi in enumerate(gen_999(949)):
        print(mbi)
        if i == 100:
            break
    else:
        print("ended before break")

if __name__ == '__main__': 
    main()

This code prints numbers from 949 to 999, and the performance hit is an extra assignment statement in each level of looping.

Answer 3

As @AustinHastings pointed out, the itertools.product solution below doesn't work right unless you start at the beginning. So here's an alternate solution:

DIGIT  =  '0123456789'
LETTER = 'ACDEFGHJKMNPQRTUVWXYZ'
DIGLET = DIGIT + LETTER

def mbi_gen(start=None):
    pattern = [DIGIT[1:],   # leading non-zero digit
               LETTER,
               DIGLET,
               DIGIT,
               LETTER,
               DIGLET,
               DIGIT,
               LETTER,
               LETTER,
               DIGIT,
               DIGIT
              ]
    if start:
        indices = [pattern[i].index(c) for i,c in enumerate(start)]
    else:
        indices = [0]*len(pattern)

    while True:
        yield ''.join(pat[i] for pat,i in zip(pattern, indices))

        for i in range(len(indices)-1, -1, -1):
            indices[i] += 1
            if indices[i] < len(pattern[i]):
                break

            indices[i] = 0

mbi_gen() is a generator and can be used like so:

MBI = mbi_gen()

for n in range(10000):
    print(next(MBI))

or to generate a list of 10000 MBIs:

MBIs = list(it.islice(mbi_gen('3C12D34EF56'), 10000)

itertools.product()

This is a task made for itertools.product(). As the docs say, product(A, B, C) is equivalent to ((a,b,c) for a in A for b in B for c in C). The c cycles the fastest, then 'b' and a is the slowest. Like an odometer.

import itertools as it

DIGIT  =  '0123456789'
LETTER = 'ACDEFGHJKMNPQRTUVWXYZ'
DIGLET = DIGIT + LETTER

def mbi_gen(start=None):
    pattern = [DIGIT[1:],   # leading non-zero digit
               LETTER,
               DIGLET,
               DIGIT,
               LETTER,
               DIGLET,
               DIGIT,
               LETTER,
               LETTER,
               DIGIT,
               DIGIT
              ]

    yield from (''.join(seq) for seq in it.product(*pattern))