I needed to write a Python generator that lazily generates, in lexicographical order, strings composed of a certain alphabet (e.g. lowercase English letters).
My first thought was to make an infinite generator, but an infinite iterator would be pretty useless because it would just generate strings composed of only the character
a. This is because the lexicographical ordering of strings is not a well-order; it can be thought of as composed of an infinite sequence of infinitely nested sequences: (
aa, ...), (
ab, ...), ...), (
ba, ...), (
bb, ...), ...), ... The generator would never reach
ab since it has an infinite amount of predecessors.
Thus I went for limiting the maximum length of the strings. I.e., the full specification is a generator that lazily generates all strings in a given alphabet of up to a certain length in lexicographical order. E.g., for a maximum length of 3 with ASCII lowercase letters, it should generate, in this order:
The solution I came up with is elegant in the abstract; it uses the intrinsic recursive relationship of lexicographical ordering: if you take the set of all strings—including infinite strings—and remove the first character from each, you're still left with the set of all strings. But it's probably not very efficient in practice, as for each iteration it uses Python's string concatenation operation
+ \$m\$ times to build a string of length \$m\$ (\$m - 1\$ times in between characters plus the "terminating" empty string, as you'll see below), and strings are immutable so copies are made at every intermediate step, resulting in \$O(m^2)\$ time complexity at each iteration.
Here is my solution:
import string def lexstrings(max_length: int, alphabet=string.ascii_lowercase): yield "" if max_length == 0: return for first in alphabet: for suffix in lexstrings(max_length - 1, alphabet=alphabet): yield first + suffix
>>> g = lexstrings(max_length=3, alphabet="ab") >>> list(g) ['', 'a', 'aa', 'aaa', 'aab', 'ab', 'aba', 'abb', 'b', 'ba', 'baa', 'bab', 'bb', 'bba', 'bbb']
This implementation also "supports" the infinite version by supplying a negative maximum length:
>>> g = lexstrings(-1) >>> next(g) '' >>> next(g) 'a' >>> next(g) 'aa' >>> next(g) 'aaa' ...
Some benchmarking confirms a single iteration of this is quadratic in terms of the string size. Here is a plot of execution time for generating a string of maximum length (in a single iteration) vs the maximum length:
The code to generate this plot using
perfplot follows. (I modified the order of generation so that the first iteration yields a max-length string.)
import string import perfplot import sys import numpy as np def lexstrings(max_length: int, alphabet=string.ascii_lowercase): if max_length == 0: return for first in alphabet: for suffix in lexstrings(max_length - 1, alphabet=alphabet): yield first + suffix yield "" n_range = np.linspace(1, sys.getrecursionlimit() - 500) benchmark = perfplot.bench( setup=lambda n: n, kernels=[ lambda n: next(lexstrings(n)), ], labels=[ "lexstrings", ], n_range=n_range, xlabel="maximum string length", title="Single iteration (max-length string)", target_time_per_measurement=0.1, equality_check=None, ) benchmark.show(logx=False, logy=False)