2

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

目前，我有一个使用嵌套 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))

列表（变量字符串完成（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)]
4

2 回答 2

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

于 2015-03-18T06:02:23.110 回答
0

这似乎有效（编辑——将其固定为生成器）：

from itertools import chain

def variable_strings_complete(max_len, alphabet=range(2)):
    alphabet = sorted(map(str, alphabet))

    def complete_partial(partial, alph_idx):
        to_returns = (partial + a for a in alphabet)

        if alph_idx == (max_len - 1):
            yield from to_returns
        else:
            for r in to_returns:
                n = complete_partial(r, alph_idx + 1)
                yield from chain([r], n)

    yield from complete_partial("", 0)

print(list(variable_strings_complete(3)))

回报：

['0', '00', '000', '001', '01', '010', '011', '1', '10', '100', '101', '11', '110', '111']

它适用于其他字母：

print(list(variable_strings_complete(3, "ab")))

产量

['a', 'aa', 'aaa', 'aab', 'ab', 'aba', 'abb', 'b', 'ba', 'baa', 'bab', 'bb', 'bba', 'bbb']
于 2015-03-18T05:40:44.207 回答