@jinxonik / UniLecs #126

Comb123.py

def comb_count1(str_len):
  """ МЕТОД 1 ***
  Строка состоит из 1, 2 и/или 3, значит и начинаться она может с этих цифр.
  После 2 и 3 могут идти любые цифры, поэтому считаем кол-во комбинаций всех
  оставшихся цифр (для N-1) и умножаем его на 2 (т.е. для начальной 2 и 3).
  После цифры 1 может идти только 1 или 3, при этом после 3 могут идти любые
  цифры, а после 1 ситуация повторяется, поэтому мы считаем комбинации для
  N-2, N-3, N-4... 1 (подсчёт реализован в обратном порядке).
  Также добавляем комбинации, полностью состоящие из единиц или с 3 в конце.
  Для ускорения работы кэшируем результат.
  """
  if str_len < 0: return None
  cc = {0:0, 1:3}  # предопределённые значения (он же кэш)

  def comb(str_len):
    if str_len in cc: return cc[str_len]  # берём значение из кэша
    count = 2  # все единицы и все единицы с 3 на конце (например, 111, 113)
    # Считаем варианты 13.., 113.., 1113.. и т.д.
    for i in range(1, str_len-1):
      count += comb(i)
    # Добавляем 2.., 3..
    count += 2 * comb(str_len-1)
    # Кэшируем результат
    cc[str_len] = count
    return count

  return comb(str_len)

def comb_count2(str_len):
  """ МЕТОД 2 ***
  В этом варианте рекурсивная функция имеет дополнительный параметр - deny2,
  который означает, что рассчитываемая комбинация не должна начинаться с 2.
  Кол-во комбинаций для оставшихся цифр (N-1) мы умножаем на 2 только в том
  случае, если deny2 = False. Для поиска кол-ва комбинаций для значений,
  начинающихся с 1, мы вызываем рекурсивную функцию с N-1 и deny2 = True.
  Результаты кэшируются отдельно для deny2 = True и для deny2 = False.
  """
  if str_len < 0: return None
  # Предопределённые значения (он же кэш)
  cc = {True: {0:0, 1:2},  # для deny2 = True
       False: {0:0, 1:3}}  # для deny2 = False

  def comb(str_len, deny2):
    if str_len in cc[deny2]: return cc[deny2][str_len]  # берём из кэша
    # Считаем варианты для 3...
    count = comb(str_len-1, False)
    # Добавляем варианты для 2..., если они не запрещены
    if not deny2: count *= 2
    # Добавляем варианты для 1...
    count += comb(str_len-1, True)
    # Кэшируем результат
    cc[deny2][str_len] = count
    return count

  return comb(str_len, False)

def comb_count3(str_len):
  """ МЕТОД 3 ***
  Кол-во вариантов можно рассчитать так: 3*F(N-1) - F(N-2), т.е. для каждой
  начальной цифры вычисляем кол-во вариантов для оставшейся части строки
  (т.е. для N-1) и вычитаем из этого числа для сочетания 12 кол-во вариантов
  для оставшейся части строки (т.е. для N-2).
  Что интересно, эта формула является формулой чисел Фибоначчи, стоящих на
  чётных позициях (т.е. F(N) = fib(2*N)).
  Числа Фибоначчи можно вычислить обычным циклом без рекурсии (и без кэшей).
  """
  if str_len < 0: return None
  if str_len == 0: return 0
  n = [0, 1]
  for i in range(str_len):
    n = [n[1], n[1]*3-n[0]]
  return n[1]

# Проверка ответа простым перебором вариантов
from itertools import product
def comb_count_check(str_len):
  n = 0
  for x in product('123', repeat=str_len):
    if ''.join(x).find('12') == -1: n += 1
  return n

############################################################################

for n in (1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15, 20, 25, 30, 50, 100):
  s = f'N = {n}, comb1 = {comb_count1(n)}, comb2 = {comb_count2(n)}, ' \
      f'comb3 = {comb_count3(n)}, brute-force = '
  if n <= 12:
    s += f'{comb_count_check(n)}'
  else:
    s += 'too slow :('
  print(s)