python - Itertools 停止连续重复的字符

Question

我编写了以下代码，使所有 20 个字符长的字符串都包含 A、T、G 和 C 的组合。

但是，我想避免连续出现 3 个以上的相同字符，因此我添加了一个 if 函数来检查这一点。问题是，这是在 itertools 代码之后，所以有点慢。我想知道是否有一种方法可以使用 itertools 来产生这个结果，而不必运行 itertools 然后运行 ​​if 函数？

import sys
import itertools
import re

x = ["A","T","G","C"]
for i in itertools.product(x, repeat=20):
        i = "".join(i)
        if re.search(r"(\w)\1\1",i):
                continue
        else:
                sys.stdout.write(i)

Answer 1

从表面上看，问题似乎是在问:

How can I filter this enormous list of strings without the pain of having to construct the whole list first?

答案是:你已经在这么做了! itertools 中的东西生成以迭代方式构造的延迟生成的序列。因此，您现有的代码不会生成包含数十亿个字符串的庞大列表。​​

但是您可能想问一个可能更有趣的问题:

If I generate the triplet-free strings by generating all the strings and filtering out the ones with triplets in, my code is having to do extra work because most of the strings generated will have triplets in them. Suppose the strings are generated in lexicographic order; then the first 4**17 of them will begin AAA, and we really ought to be able to skip over all of those. How can we do better?

不幸的是，如果您想这样做那么您将必须编写自己的代码来做到这一点； itertools 不提供这种“模式过滤产品”功能。

它可能看起来像这样:

# generate all n-tuples with the property that their k-th element
# is one of the things returned by successors(initial (k-1)-tuple).
# So e.g. the first element is one of the things returned by
# successors(()).
def restricted_tuples(successors, n):
    assert(n>=0)
    if n==0:
        for t in successors(()): yield (t,)
    else:
        for start in restricted_tuples(successors, n-1):
            for t in successors(start): yield start+(t,)

def successors_no_triples(start, alphabet):
    if len(start)<2 or start[-1] != start[-2]:
        for t in alphabet: yield t
    else:
        banned = start[-1]
        for t in alphabet:
            if t != banned: yield t

print([''.join(x) for x in restricted_tuples(lambda start: successors_no_triples(start,'ABC'), 5)])

最后的print仅供说明。如果您想打印出原始提问者案例中的所有数十亿个字符串，您最好迭代 restricted_tuples 生成的序列，并分别对每个字符串进行字符串化和打印。

顺便说一句，具有此属性的 4 个字母上长度为 20 的序列的数量结果为 415,289,569,968。如果您尝试生成所有这些，您将需要等待一段时间，特别是如果您实际上想对每个做任何事情。