时间戳

首页 > 解决方案 > 如何在 Python 中遍历所有单词直至字母表的排列？

python - 如何在 Python 中遍历所有单词直至字母表的排列？

问题描述

对我来说，这似乎不是一个小众问题，但令人惊讶的是，我在网上找不到任何关于它的信息。假设您有一个字母集（对我来说是常用字母的前 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 中似乎没有命令以这种方式进行迭代

很容易拼凑一些代码，在每个新单词长度的开头，将所有该长度的单词存储在一个列表中，根据字母表的排列精简列表，然后将该列表变成一个iterable 可被迭代。问题是随着单词的长度变大，这个列表将不适合内存。谢谢。

标签： pythoniterationpermutationitertoolsalphabet

解决方案

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

基本上，我们只想要不能被凯撒密码的字符串转换成字典上更小的字符串。我没有正式的证明，但我怀疑这些字符串总是满足特定的属性：字符串中第一次出现的字符永远不会出现在字典序较大的字符之后。例如，"abbacb"满足此属性，因为 firsta出现在 first 之前b，并且 firstb出现在 first 之前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

推荐阅读