如何排列30个字符的二进制字符串并省略“错误字符串”

debugcn 发表于 Dev

尼古拉斯·奥多尼亚

我输入字符串的长度（10或30或...），然后输入“坏字符串”“ 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)))

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)))

输出