如何在Python中遍历所有单词，直到字母表的排列？
如何在Python中遍历所有单词，直到字母表的排列？
提问于 2019-04-16 01:31:07
对我来说，这似乎不是一个小众问题，但令人惊讶的是，我在网上找不到任何关于它的东西。假设您有一个字母集(对我来说是常用字母表的前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中似乎没有用于以这种方式迭代的命令
很容易拼凑一些代码，在每个新单词长度的开始，将该长度的所有单词存储在列表中，根据字母表的排列来精简列表，然后使该列表成为可迭代的迭代。问题是，随着单词的长度变大，这个列表将无法存储在内存中。谢谢。
回答 1
Stack Overflow用户
发布于 2019-04-16 03:57:47
我认为用少量的内存就可以做到这一点。我估计所需的内存与生成的字符串的长度成正比。
基本上，我们只想要那些不能被Caesar加密的字符串，这些字符串的字典顺序更小。我没有正式的证明，但我怀疑这些字符串总是满足一个特定的属性:字符串中第一个出现的字符永远不会出现在字典顺序较大的字符之后。例如，"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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/55694495
复制相关文章
相似问题
腾讯云开发者
