按 Python 中的字典顺序生成字符串

Question

如何编写一个 Python 生成器延迟生成所有由小写英文字母组成的不超过一定长度的字符串¹?

我已经编写了自己的解决方案 ()，但我想看看是否还有其他 elegant/efficient/fun 解决方案。

¹ 无限迭代器将毫无用处，因为它只会生成仅由字符 a 组成的字符串。这是因为字符串的字典顺序不是 well-order；它可以被认为是由无限嵌套序列的无限序列组成的：(a, (aa, ...), (ab, ...), ... ), (b, (ba, ...), (bb, ...), ...), ... 生成器永远不会达到 ab 因为它有无限多的前辈。

Answer 1

这是我的解决方案：

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']

这可能不是最佳解决方案，因为它涉及递归并使用 + 运算符 m 次来生成长度为 m 的字符串，效率不高，因为 Python 生成中间结果的副本（因为字符串是不可变的）。

此实现还“支持”无限版本：

>>> g = lexstrings(-1)
>>> next(g)
''
>>> next(g)
'a'
>>> next(g)
'aa'
>>> next(g)
'aaa'
...

按 Python 中的字典顺序生成字符串

Generate strings in lexicographical order in Python

python

generator

lazy-sequences

lexicographic