Итератор для всех лексикографически упорядоченных строк переменных до длины n

Я пытаюсь создать итератор/генератор всех строк переменной длины с учетом алфавита и максимальной длины строки, отсортированных в лексикографическом порядке.

В настоящее время у меня есть наивный метод, который использует вложенный продукт itertools(), а затем приступает к сортировке. Это прекрасно работает для небольшого 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)]

python lexicographic
person Community    schedule 18.03.2015    source источник
comment
Вам нужны все возможные строки длины 32? Все 1 901 722 457 268 488 241 418 827 816 020 396 748 021 170 176 из них, при условии, что мы рассматриваем только строчные буквы и без пробелов?!   -  person Two-Bit Alchemist    schedule 18.03.2015
comment
Ну немного строк. Гораздо разумнее.   -  person Two-Bit Alchemist    schedule 18.03.2015
comment
Вы хотите, чтобы это было только для {0, 1}, или это должно работать в целом?   -  person Patrick Collins    schedule 18.03.2015

Ответы (2)


arrow_upward
1
arrow_downward

Работать с 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, если это не так.

person DSM    schedule 18.03.2015

arrow_upward
0
arrow_downward

Кажется, это работает (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']
person Patrick Collins    schedule 18.03.2015
comment
@JoelSnyder Без обид - ответ выше меня более полный. - person Patrick Collins; 18.03.2015