Lazy generator of strings in lexicographical order 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: (a, (aa, ...), (ab, ...), ...), (b, (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: &quot;&quot;, &quot;a&quot;, &quot;aa&quot;, &quot;aaa&quot;, &quot;aab&quot;, ..., &quot;aaz&quot;, &quot;ab&quot;, &quot;aba&quot;, ..., &quot;zzz&quot;.
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 &quot;terminating&quot; 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 &quot;&quot;
    if max_length == 0: return
    for first in alphabet:
        for suffix in lexstrings(max_length - 1, alphabet=alphabet):
            yield first + suffix

Example:
&gt;&gt;&gt; g = lexstrings(max_length=3, alphabet=&quot;ab&quot;)
&gt;&gt;&gt; list(g)
['',
 'a',
 'aa',
 'aaa',
 'aab',
 'ab',
 'aba',
 'abb',
 'b',
 'ba',
 'baa',
 'bab',
 'bb',
 'bba',
 'bbb']

This implementation also &quot;supports&quot; the infinite version by supplying a negative maximum length:
&gt;&gt;&gt; g = lexstrings(-1)
&gt;&gt;&gt; next(g)
''
&gt;&gt;&gt; next(g)
'a'
&gt;&gt;&gt; next(g)
'aa'
&gt;&gt;&gt; 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 &quot;&quot;


n_range = np.linspace(1, sys.getrecursionlimit() - 500)
benchmark = perfplot.bench(
    setup=lambda n: n,
    kernels=[
        lambda n: next(lexstrings(n)),
    ],
    labels=[
        &quot;lexstrings&quot;,
    ],
    n_range=n_range,
    xlabel=&quot;maximum string length&quot;,
    title=&quot;Single iteration (max-length string)&quot;,
    target_time_per_measurement=0.1,
    equality_check=None,
)


benchmark.show(logx=False, logy=False)
It's a great question, and the only improvements I can see are superficial ones:

Your method has incomplete type hints. alphabet should be Iterable[str], and it should return -&gt; Iterable[str] as well.
PEP8 discourages multi-statement lines (your return).

Otherwise, you should reconsider making this a recursive implementation. I see that you were careful to check sys.getrecursionlimit() in your test code, so you're already aware of the fact that this will break given sufficient depth. Python also does not have tail optimization so an iterative implementation will potentially yield performance improvements.