时间戳

首页 > 解决方案 > 在 Python 中按字典顺序生成字符串

python - 在 Python 中按字典顺序生成字符串

问题描述

如何编写一个 Python 生成器，它可以懒惰地生成由不超过一定长度1的小写英文字母组成的所有字符串？

我已经编写了自己的解决方案（作为答案发布在下面），但我想看看是否有更优雅/高效/有趣的解决方案。

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

标签： pythongeneratorlazy-sequenceslexicographic

解决方案

这是我的解决方案：

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 might not be the best solution because it involves recursion and using the + operator m times to generate a string of length m, which isn't efficient because Python generates copies of the intermediate results (since strings are immutable).

This implementation also "supports" the infinite version:

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

推荐阅读