有限生成的词

Question

我想做一个算法，它可以生成长度小于或等于 n 的单词，不包含某些字符串，并且在我生成长度单词时用不到一两分钟的时间生成所有单词15 个或更多。我生成它们的实际代码是这样的：

def inv(mob):
    if 'aA' in mob:
        return False
    elif 'Aa' in mob:
        return False
    elif 'Bb' in mob:
        return False
    elif 'bB' in mob:
        return False
    else: return True

S=itertools.product('AaBb',repeat=n)

SS=map(lambda x: ''.join(x),S)

SSS=filter(inv,SS)

（其中 n 是长度）当我创建长度为 n=10 的单词时，需要 3 秒，但我需要在不到一分钟的时间内生成至少长度为 n=15 的单词，当我尝试使用 n=15 时，我的计算机死机了。有人知道是否存在简单的方法？或者这道题的出词时间不能少于2分钟？

Answer 1

使用 itertools.imap 和 itertools.ifilter 而不是 map 和 filter 函数，因为它们生成可迭代对象而不是列表。这应该允许避免创建 map 产生的大列表，该列表必须包含 1073741824 (4**15) 个元素。

S = itertools.product('AaBb', repeat=n)
SS = itertools.imap(lambda x: ''.join(x), S)
SSS = itertools.ifilter(inv, SS)

有限生成的词

Finitely generated words

sage

itertools

python-2.7