python - 所有按字典顺序排列的可变字符串的迭代器，长度不超过 n

Question

我正在尝试为给定字母表和最大字符串长度并按字典顺序排序的所有可变长度字符串创建一个迭代器/生成器。

目前，我有一个简单的方法，它使用嵌套的 itertools product()，然后进行排序。这对于较小的 max_len_string 非常有效，但对于我的目标用途(大约 max_len_string=32)，这使用了太多的临时存储空间而不实用。

有没有办法让这个算法每次迭代只使用少量的常量空间，而不是在排序时吞噬整个序列？

from itertools import product
def variable_strings_complete(max_len_string, alphabet=range(2)):
    yield from sorted(string
                      for i in range(1, max_len_string+1)
                      for string in product(alphabet, repeat=i))

列表(variable_strings_complete(3))

[(0,),
 (0, 0),
 (0, 0, 0),
 (0, 0, 1),
 (0, 1),
 (0, 1, 0),
 (0, 1, 1),
 (1,),
 (1, 0),
 (1, 0, 0),
 (1, 0, 1),
 (1, 1),
 (1, 1, 0),
 (1, 1, 1)]

Answer 1

一大早使用 itertools 是灾难的根源，但是像这样的东西

from itertools import product, takewhile
def new(max_len_string, alphabet=range(2)):
    alphabet = list(alphabet)
    zero = alphabet[0]
    for p in product(alphabet, repeat=max_len_string):
        right_zeros = sum(1 for _ in takewhile(lambda x: x==zero, reversed(p)))
        base = p[:-right_zeros]
        yield from filter(None, (base+(zero,)*i for i in range(right_zeros)))
        yield p

应该工作:

>>> list(new(3)) == list(variable_strings_complete(3))
True
>>> list(new(20)) == list(variable_strings_complete(20))
True
>>> list(new(10, alphabet=range(4))) == list(variable_strings_complete(10, range(4)))
True

这假设字母表是按规范顺序传递的；如果不是这样，list 可以替换为 sorted。