Как мне перебрать все слова вплоть до перестановки алфавита в Python?

Question

Это не кажется мне нишевой проблемой, но я удивительно не могу найти что-либо об этом в Интернете.Предположим, у вас есть набор алфавита (для меня первые m букв обычного алфавита), и вы хотите эффективно перебрать все слова алфавита (например, для того, чтобы провести их анализ).Это легко сделать в Python;просто сделайте что-то вроде

import itertools
alphabet = 'abcdefghijklmnopqrstuvwxyz'[0:m]
for l in range(0, 200):
    for word in itertools.product(alphabet, repeat=l):
        #foo

Однако для моей конкретной проблемы, когда я делаю анализ строки, легко предсказать, как изменится ответ, когда я применю к строке перестановку алфавита.Скорость имеет решающее значение в моей программе, поэтому нет смысла перебирать все слов;если бы я мог перебирать слова с точностью до перестановок алфавита , то я мог бы уменьшить пространство поиска и, следовательно, скорость с коэффициентом фактора len (алфавит) (в моем случае это также означало бы, что у меня меньше данных вобъем памяти).Я посмотрел, и в itertools, похоже, нет команды для итерации таким образом

Было бы легко собрать воедино некоторый код, который в начале каждой новой длины слова хранит всеслова такой длины в списке, сокращают список по отношению к перестановкам алфавита, а затем превращают этот список в итеративный для повторения.Проблема заключается в том, что, поскольку длина слов становится большой, этот список не умещается в памяти.Благодаря.

Answer 1

Я думаю, что это можно сделать с небольшим объемом памяти. Я считаю, что объем необходимой памяти пропорционален длине генерируемой строки.

В основном нам нужны только строки, которые не могут быть зашифрованы Цезарем в строку, которая лексикографически меньше. У меня нет формального доказательства, но я подозреваю, что эти строки всегда удовлетворяют определенному свойству: первое вхождение символа в строке никогда не появляется после символа, который лексикографически больше. Например, "abbacb" удовлетворяет этому свойству, потому что первый a появляется перед первым b, а первый b появляется перед первым c. С этим свойством должна быть возможность рекурсивно генерировать все такие строки, начиная с самой маленькой.

def gen_words(alphabet, size=None):
    if size is None:
        i = 0
        while True:
            yield from gen_words(alphabet, i)
            i += 1
    if size == 0:
        yield ""
    else:
        for s in gen_words(alphabet, size-1):
            #determine which characters are permissible.
            used_characters = sorted(set(s))
            #any character that has already been used is permissible.
            for c in used_characters:
                yield s + c
            #the lexicographically smallest unusued character is also permissible.
            if len(used_characters) < len(alphabet):
                yield s + alphabet[len(used_characters)]

g = gen_words("ab")
for i in range(20):
    print(next(g))

#or, to generate an infinite number os trings, use:
#for s in gen_words("ab"):
#    print(s)

Результат:

a
aa
ab
aaa
aab
aba
abb
aaaa
aaab
aaba
aabb
abaa
abab
abba
abbb
aaaaa
aaaab
aaaba
aaabb