Найти все комбинации, которые не содержат заданную строку c

Question

Есть ли способ найти все комбинации массива, который не содержит указанных c подстрок? Например, 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

Вместо генерации всех строк с последующим отклонением тех, которые содержат любые запрещенные подстроки, (асимптотически) более эффективно создавать строки путем обратного отслеживания и отклонять любую частичную строку, которая уже содержит запрещенную подстроку. Нам нужно только проверить, заканчивается ли текущая частичная строка какой-либо запрещенной подстрокой, что быстрее, чем проверка, если она содержит единицу.

Вот реализация, использующая рекурсивный функция генератора:

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

Для строк длиной 13 из алфавита размера 20 это должно быть большим улучшением, но 20 ¹³ это огромное количество Поэтому, если вы не запретите много подстрок, количество решений будет очень большим. Ни один алгоритм не может генерировать h строк длиной k менее чем за O ( hk ) времени, поэтому время работы любого эффективного алгоритма все равно будет выходной чувствительный .