Итератор для всех лексикографически упорядоченных строк переменных до длины 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 если это не так.

Answer 2

Это похоже на работу (EDIT - исправлено, чтобы быть генератором):

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