python - 如何在 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(alphabet) 阶乘的速度(在我的情况下，这也意味着我有更少的数据)在内存中)。我看了一下，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