Как сделать так, чтобы список не повторял один и тот же символ три раза подряд

Question

У меня есть этот код

for letters in itertools.product(charset, repeat=47):
    string = "".join(letters)
    print(string)

и из него

aaaaaaaaaaaa
aaaaaaaaaaab
aaaaaaaaaaac

, но мне интересно, как я могу заставить его не генерировать те же три символа в строке, чтобы вывод

dddcccbbbaaa
dddcccbbbaab
dddcccbbbaac

и так далее без использования чего-либо подобного

for letters in itertools.product(charset, repeat=47):
    string = "".join(letters)
    for i in range(1,len(string)-1):
        if string[i] is not string[i+1] is not string[i-1]:
            print(string)
        else:
            pass

Answer 1

Вот немного измененная версия вашего кода:

import itertools

def version1(charset, N):
    result = []
    for letters in itertools.product(charset, repeat=N):
        string = "".join(letters)
        for i in range(0, N-2):
            if string[i] == string[i+1] == string[i+2]:
                break
        else: # did not find any ZZZ sequence
           result.append(string)
    return result

>>> charset = "abc"
>>> N = 5
>>> version1(charset, N)
['aabaa', 'aabab', 'aabac', 'aabba', 'aabbc', 'aabca', 'aabcb', 'aabcc', 'aacaa', 'aacab', 'aacac', 'aacba', 'aacbb', 'aacbc', 'aacca', 'aaccb', 'abaab', 'abaac', 'ababa', 'ababb', 'ababc', 'abaca', 'abacb', 'abacc', 'abbaa', 'abbab', 'abbac', 'abbca', 'abbcb', 'abbcc', 'abcaa', 'abcab', 'abcac', 'abcba', 'abcbb', 'abcbc', 'abcca', 'abccb', 'acaab', 'acaac', 'acaba', 'acabb', 'acabc', 'acaca', 'acacb', 'acacc', 'acbaa', 'acbab', 'acbac', 'acbba', 'acbbc', 'acbca', 'acbcb', 'acbcc', 'accaa', 'accab', 'accac', 'accba', 'accbb', 'accbc', 'baaba', 'baabb', 'baabc', 'baaca', 'baacb', 'baacc', 'babaa', 'babab', 'babac', 'babba', 'babbc', 'babca', 'babcb', 'babcc', 'bacaa', 'bacab', 'bacac', 'bacba', 'bacbb', 'bacbc', 'bacca', 'baccb', 'bbaab', 'bbaac', 'bbaba', 'bbabb', 'bbabc', 'bbaca', 'bbacb', 'bbacc', 'bbcaa', 'bbcab', 'bbcac', 'bbcba', 'bbcbb', 'bbcbc', 'bbcca', 'bbccb', 'bcaab', 'bcaac', 'bcaba', 'bcabb', 'bcabc', 'bcaca', 'bcacb', 'bcacc', 'bcbaa', 'bcbab', 'bcbac', 'bcbba', 'bcbbc', 'bcbca', 'bcbcb', 'bcbcc', 'bccaa', 'bccab', 'bccac', 'bccba', 'bccbb', 'bccbc', 'caaba', 'caabb', 'caabc', 'caaca', 'caacb', 'caacc', 'cabaa', 'cabab', 'cabac', 'cabba', 'cabbc', 'cabca', 'cabcb', 'cabcc', 'cacaa', 'cacab', 'cacac', 'cacba', 'cacbb', 'cacbc', 'cacca', 'caccb', 'cbaab', 'cbaac', 'cbaba', 'cbabb', 'cbabc', 'cbaca', 'cbacb', 'cbacc', 'cbbaa', 'cbbab', 'cbbac', 'cbbca', 'cbbcb', 'cbbcc', 'cbcaa', 'cbcab', 'cbcac', 'cbcba', 'cbcbb', 'cbcbc', 'cbcca', 'cbccb', 'ccaab', 'ccaac', 'ccaba', 'ccabb', 'ccabc', 'ccaca', 'ccacb', 'ccacc', 'ccbaa', 'ccbab', 'ccbac', 'ccbba', 'ccbbc', 'ccbca', 'ccbcb', 'ccbcc']

Ваш алгоритм не оптимален. Посмотрите на первую строку:

aaaaa

Вы знаете, что вам нужно len(charset) - 1 итераций (aaaab, aaaac), чтобы прийти к:

aaaba

И затем снова len(charset) - 1 итераций для прибыть в:

aaaca

Но вы можете пропустить все эти итерации, так как начало aaa. На самом деле, когда вы найдете последовательность aaa, вы можете пропустить len(charset)^K - 1, где K - количество оставшихся символов. Это не меняет сложность O, но сократит время вычислений для длинных последовательностей, в зависимости от размера кодировки и количества символов в строках.

Интуитивно понятно, если в кодировке мало символов , вы сэкономите много вычислений.

Сначала вам нужно найти первую букву после последовательности ZZZ:

def first_after_ZZZ(string):
     for i in range(0, len(string)-2):
         if string[i] == string[i+1] == string[i+2]:
             return i+3
     return -1

>>> first_after_ZZZ("ababa")
-1
>>> first_after_ZZZ("aaaba")
3
>>> first_after_ZZZ("aaabaaabb")
3

Мы используем эту функцию в предыдущем коде (промежуточный шаг) :

def version2(charset, N):
    result = []
    for letters in itertools.product(charset, repeat=N):
        string = "".join(letters)
        f = first_after_ZZZ(string)
        if f == -1:
            result.append(string)
    return result

>>> version2(charset, N) == version1(charset, N)
True

Теперь мы можем пропустить некоторые элементы:

def version3(charset, N):
    result = []
    it = itertools.product(charset, repeat=N)
    for letters in it:
        string = "".join(letters)
        f = first_after_ZZZ(string)
        if f == -1:
            result.append(string)
        elif f < N:
            K = N - f # K > 1
            to_skip = len(charset)**K-1 
            next(itertools.islice(it, to_skip, to_skip), None) # this will skip to_skip tuples
    return result

>>> version3(charset, N) == version1(charset, N)
True

Тест:

>>> from timeit import timeit as ti
>>> ti(lambda: version1(charset, 15), number=1)
13.14919564199954
>>> ti(lambda: version3(charset, 15), number=1)
6.94705574299951

Это впечатляет, потому что кодировка небольшая, но может быть незначительно для всего алфавита.

Конечно, если вы напишите собственную реализацию product, вы можете пропустить кортежи, не генерируя их, и это может быть быстрее.