查找不包含特定字符串的所有组合

Question

有什么方法可以找到不包含特定子字符串的数组的所有组合？例如a=['a','b','c'] aaa aab aac aba abb ... ccc

但是我不想要子字符串ab，所以aaa aac aca acb ... ccc我使用下面的代码，但是对于20字符和13的组合，这会花费太多时间

import itertools

lista=[]
def foo(l):
    yield from itertools.product(*([l] * 3)) 

non=["ab"]

for x in foo('abc'):
    x=(''.join(x))
    for j in non:
        if j in x:
            value=1
            break
        else:
            value=0
    if (value==0):
        lista.append(x)

Answer 1

不是生成所有字符串然后拒绝包含任何禁止的子字符串的字符串，而是（渐近地）通过回溯来构建字符串，并拒绝任何已经包含禁止的子字符串的部分字符串，效率更高。我们只需要测试当前部分字符串ends是否具有任何禁止的子字符串，这比测试它是否contains一个要快。

这里是使用递归生成器函数的实现：

def strings_without(alphabet, k, avoid):
    def helper(s):
        if any(s.endswith(t) for t in avoid):
            pass
        elif len(s) == k:
            yield s
        else:
            for c in alphabet:
                yield from helper(s + c)
    return helper('')

示例：

>>> for s in strings_without('abc', 3, ['ab']):
...     print(s)
... 
aaa
aac
aca
acb
acc
baa
bac
bba
bbb
bbc
bca
bcb
bcc
caa
cac
cba
cbb
cbc
cca
ccb
ccc

对于大小为20的字母的长度为13的字符串，这应该是一个很大的改进，但是20 ¹³是一个巨大的数字。因此，除非您禁止使用许多子字符串，否则解决方案的数量将非常大。没有任何算法可以在少于O（hk）时间内生成长度为[[k的h个字符串，因此任何有效算法的运行时间仍为output-sensitive。