如何在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

我认为用少量内存可以做到这一点。我估计所需的内存与生成的字符串的长度成正比。

基本上我们只想要不能将Caesar-Ciphered的字符串放入字典缩小的字符串中。我没有正式的证据，但我怀疑这些字符串总是满足一个特定的属性：字符串中第一次出现的字符永远不会出现在字典大字的字符之后。例如，"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