Здравствуйте, подскажите, пожалуйста решение задачи:
(№ 5073) (Н. Вольхин) Николай составляет слова из букв C, O, N, S, T. Каждый символ в последовательности может встречаться любое количество раз или не встречаться совсем. Слова должны удовлетворять следующим условиям:
1) не содержат двух одинаковых букв, стоящих рядом;
2) буква S не может быть первой и последней в слове;
3) буква S может находится только между двумя разными буквами.
Сколько различных 16-буквенных слов может составить Николай?
Не пойму по какому алгоритму её решать
Простым перебором не получается, так как очень большой список получается:
from itertools import *
l = set(map(''.join, product('CONST', repeat=16)))
count = 0
for x in l:
if 'CC' not in x and 'OO' not in x and 'NN' not in x and 'SS' not in x and 'TT' not in x\
and x[0] != 'S' and x[15] != 'S' and \
'CSC' not in x and 'OSO' not in x and 'NSN' not in x and 'TST' not in x:
count += 1
print(count)
Пытался сделать таким же способом, как здесь:
https://youtu.be/btX4IOUjF08
from itertools import *
n = 10
for j in range(1, n):
l = set(map(''.join, product('CONST', repeat=j)))
count = 0
for x in l:
if 'CC' not in x and 'OO' not in x and 'NN' not in x and 'SS' not in x and 'TT' not in x\
and x[0] != 'S' and x[j - 1] != 'S' and \
'CSC' not in x and 'OSO' not in x and 'NSN' not in x and 'TST' not in x:
count += 1
print(count)
Вывод:
4
12
48
180
684
2592
9828
37260
141264
Отношение к предыдущему различное:
4 : 4.0
12 : 3.0
48 : 4.0
180 : 3.75
684 : 3.8
2592 : 3.789473684210526
9828 : 3.7916666666666665
37260 : 3.791208791208791
141264 : 3.791304347826087
В итоге закономерности не вижу