如何排列 30 个字符的二进制字符串并省略 "bad strings"

Question

我输入字符串的长度（10或30或...）并输入"bad strings"“101”、“111”，并计算不包含坏字符串的排列数。

我用 itertools 尝试了这个，它对 10-15 的字符串工作正常，但对于 30，它的结果超过一万亿，不能有效地运行。我认为方法是一次构建一个字符的字符串，但我无法弄清楚执行此操作的算法。

import itertools
v1="111"
v2="101"
def perms(n):
    for i in range(2**n):
        s=bin(i)[2:]
        s="0"*(n-len(s)) + s
        if v1 not in s and v2 not in s:
            print(s)
            yield s
print len(list(perms(10)))

Answer 1

您可以一点一点地构建字符串，立即避免错误的路径。这是一个迭代版本：

def build(n):
    strings = ['']
    bad = '111', '101'
    for _ in range(n):
        strings = [s + bit
                   for s in strings
                   for bit in '01'
                   if not (s + bit).endswith(bad)]
    return strings

这在一瞬间确认了 10 位的 169，大约需要 3.4 秒才能找到 2550409 个 30 位的字符串。

>>> len(build(10))
169
>>> len(build(30))
2550409

也可以使用嵌套生成器来节省内存：

def build(n):
    strings = ['']
    bad = '111', '101'
    for _ in range(n):
        strings = (s + bit
                   for s in strings
                   for bit in '01'
                   if not (s + bit).endswith(bad))
    return strings

演示，我也花了大约 3.4 秒：

>>> len(list(build(30)))
2550409

或者，递归版本：

def build(n, prefix=''):
    if n == 0:
        yield prefix
        return
    for bit in '01':
        if not (prefix + bit).endswith(('111', '101')):
            yield from build(n - 1, prefix + bit)

在大约七秒内找到 30 位的 2550409：

>>> len(list(build(30)))
2550409

对于 Python 2，将 yield from 行替换为：

            for bits in build(n - 1, prefix + bit):
                yield bits

如果我绕过一个输出列表而不是让出所有级别，我大约需要 4.5 秒：

def build(n, output, prefix=''):
    if n == 0:
        output.append(prefix)
        return
    for bit in '01':
        if not (prefix + bit).endswith(('111', '101')):
            build(n - 1, output, prefix + bit)

演示：

>>> output = []
>>> build(30, output)
>>> len(output)
2550409

Answer 2

这是另一个解决方案。它在我的旧机器上比 Stefan 的代码运行稍微快。

我们遍历数字，使用 str.format 方法将它们转换为位串。当我们找到一个带有错误模式的位串时，我们会跳到第一个在该位位置不包含该模式的数字。因此，如果我们发现一个坏模式结束于位串的 2**0 位位置（LSB），我们前进 1，如果坏模式结束于 2**1 位位置，我们前进 2，等等。

这是一个在循环中调用打印的版本，因此我们可以看到发生了什么。

def skip_bad(width, bad=("101", "111")):
    n = 0
    while n < 1<<width:
        s = '{0:0{1}b}'.format(n, width)
        for b in bad:
            i = s.find(b)
            if i != -1:
                i = width - i - len(b)
                print('skipping', s, i)
                n += 1 << i
                break
        else:
            yield s
            n += 1

for i in skip_bad(5):
    print(i)

输出

00000
00001
00010
00011
00100
skipping 00101 0
00110
skipping 00111 0
01000
01001
skipping 01010 1
01100
skipping 01101 0
skipping 01110 1
10000
10001
10010
10011
skipping 10100 2
11000
11001
skipping 11010 1
skipping 11100 2

这是我用来获取评论中给出的时间数据的版本。

def skip_bad(width, bad=("101", "111")):
    n = 0
    while n < 1<<width:
        s = '{0:0{1}b}'.format(n, width)
        for b in bad:
            i = s.find(b)
            if i != -1:
                n += 1 << (width - i - len(b))
                break
        else:
            yield s
            n += 1

width = 30
print(width)
print(sum(1 for _ in skip_bad(width)))

输出

30
2550409

如何排列 30 个字符的二进制字符串并省略 "bad strings"

How do I permutate a binary string of 30 characters and omit "bad strings"

python

permutation