Найдите подстроку, избегая использования рекурсивной функции

Question

Я изучаю алгоритмы в Python и решаю следующий вопрос:

Пусть x (k) будет рекурсивно определенной строкой с базовым случаем x (1) = "123" и x (k) равно «1» + x (k-1) + «2» + x (k-1) + «3». Даны три натуральных числа k, s и t, найдите подстроку x (k) [s: t].

Например, если k = 2, s = 1 и t = 5, x (2) = 112321233 и x (2) [1: 5] = 1232.

Я решил это с помощью простой рекурсивной функции:

   def generate_string(k):
        if k == 1:
            return "123"
            
        part = generate_string(k -1)
        return ("1" + part  + "2" + part + "3")
        print(generate_string(k)[s,t])

Хотя мой первый подход дает правильный ответ проблема в том, что построение строки x занимает слишком много времени, если k больше 20. Программа должна быть завершена в течение 16 секунд, пока k меньше 50. Я пытался использовать мемоизацию, но это не помогает, поскольку я не разрешено кэшировать каждый тестовый пример. Таким образом, я считаю, что должен избегать использования рекурсивных функций для ускорения программы. Есть ли какие-то подходы, которые мне следует рассмотреть?

Answer 1

Мы видим, что строка, представленная x(k), экспоненциально растет в длину с увеличением k :

len(x(1)) == 3
len(x(k)) == len(x(k-1)) * 2 + 3

Итак:

len(x(k)) == 3 * (2**k - 1)

For k равно 100, это составляет длину более 10 ³⁰ . Это больше символов, чем атомов в человеческом теле! вам не нужно создавать всю строку. Вы все равно можете использовать рекурсию, но продолжайте передавать диапазон s и t для каждого вызова. Затем, когда вы увидите, что этот фрагмент на самом деле будет вне строки, которую вы создадите, тогда вы можете просто выйти, не возвращаясь глубже, сохраняя лот времени и (строковое) пространство.

Вот как вы могли бы это сделать:

def getslice(k, s, t):
    def recur(xsize, s, t):
        if xsize == 0 or s >= xsize or t <= 0:
            return ""
        smaller = (xsize - 3) // 2
        return ( ("1" if s <= 0 else "")
               + recur(smaller, s-1, t-1)
               + ("2" if s <= smaller+1 < t else "")
               + recur(smaller, s-smaller-2, t-smaller-2)
               + ("3" if t >= xsize else "") )
    return recur(3 * (2**k - 1), s, t)

Это не требует кеширования x(k) результатов ... В моих тестах это было достаточно быстро.

Answer 2

Это интересная проблема. Я не уверен, успею ли я написать код, но вот схема того, как вы можете это решить. Примечание : см. Лучший ответ от trincot .

Как обсуждалось в комментариях, вы не можете сгенерировать фактическую строку: у вас быстро закончится память, как k растет. Но вы можете легко вычислить длину этой строки.

Сначала некоторые обозначения:

f(k) : The generated string.
n(k) : The length of f(k).
nk1  : n(k-1), which is used several times in table below.

В целях обсуждения мы можем разделить строку на следующие области. Для начальных / конечных значений используется стандартная нумерация срезов Python:

Region | Start         | End           | Len | Subtring | Ex: k = 2
-------------------------------------------------------------------
A      | 0             | 1             | 1   | 1        | 0:1  1
B      | 1             | 1 + nk1       | nk1 | f(k-1)   | 1:4  123
C      | 1 + nk1       | 2 + nk1       | 1   | 2        | 4:5  2
D      | 2 + nk1       | 2 + nk1 + nk1 | nk1 | f(k-1)   | 5:8  123
E      | 2 + nk1 + nk1 | 3 + nk1 + nk1 | 1   | 3        | 8:9  3

Учитывая k, s и t, нам нужно выяснить, какая область строки является релевантной. Возьмем небольшой пример:

k=2, s=6, and t=8.

The substring defined by 6:8 does not require the full f(k). We only need
region D, so we can turn our attention to f(k-1).

To make the shift from k=2 to k=1, we need to adjust s and t: specifically,
we need to subtract the total length of regions A + B + C. For k=2, that
length is 5 (1 + nk1 + 1).

Now we are dealing with: k=1, s=1, and t=3.

Repeat as needed.

Когда k становится достаточно маленьким, мы прекращаем эту ерунду и фактически генерируем строку, чтобы мы могли напрямую получить необходимую подстроку.

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

Answer 3

Вот итеративная версия с комментариями в JavaScript, которую очень легко преобразовать в Python.

Помимо того, что вы просили, это нерекурсивно, оно позволяет нам решать такие вещи, как f(10000, 10000, 10050), что, кажется, превышает Python глубину рекурсии по умолчанию.

// Generates the full string
function g(k){
  if (k == 1)
    return "123";
  prev = g(k - 1);
  return "1" + prev + "2" + prev + "3";
}

function size(k){
  return 3 * ((1 << k) - 1);
}

// Given a depth and index,
// we'd like (1) a string to
// output, (2) the possible next
// part of the same depth to
// push to the stack, and (3)
// possibly the current section
// mapped deeper to also push to
// the stack. (2) and (3) can be
// in a single list.
function getParams(depth, i){
  const psize = size(depth - 1);

  if (i == 0){
    return ["1", [[depth, 1 + psize], [depth - 1, 0]]];
    
  } else if (i < 1 + psize){
    return ["", [[depth, 1 + psize], [depth - 1, i - 1]]];
    
  } else if (i == 1 + psize){
    return ["2", [[depth, 2 + 2 * psize], [depth - 1, 0]]];
    
  } else if (i < 2 + 2 * psize){
    return ["", [[depth, 2 + 2 * psize], [depth - 1, i - 2 - psize]]];
    
  } else {
    return ["3", []];
  }
}

function f(k, s, t){
  let len = t - s;
  let str = "";
  let stack = [[k, s]];
  
  while (str.length < len){
    const [depth, i] = stack.pop();

    if (depth == 1){
      const toTake = Math.min(3 - i, len - str.length);
      str = str + "123".substr(i, toTake);
      
    } else {
      const [s, rest] = getParams(depth, i);
      str = str + s;
      stack.push(...rest);
    }
  }
  
  return str;
}

function test(k, s, t){
  const l = g(k).substring(s, t);
  const r = f(k, s, t);
  console.log(g(k).length);
  //console.log(g(k))
  console.log(l);
  console.log(r);
  console.log(l == r);
}

test(1, 0, 3);
test(2, 2, 6);
test(2, 1, 5);
test(4, 44, 45);
test(5, 30, 40);
test(7, 100, 150);

Answer 4

На основе ответа @ FM c , вот код python3, который вычисляет x(k, s, t):

from functools import lru_cache
from typing import *


def f_len(k) -> int:
    return 3 * ((2 ** k) - 1)


@lru_cache(None)
def f(k) -> str:
    if k == 1:
        return "123"
    return "1" + f(k - 1) + "2" + f(k - 1) + "3"


def substring_(k, s, t, output) -> None:
    # Empty substring.
    if s >= t or k == 0:
        return

    # (An optimization):
    # If all the characters need to be included, just calculate the string and cache it.
    if s == 0 and t == f_len(k):
        output.append(f(k))
        return

    if s == 0:
        output.append("1")

    sub_len = f_len(k - 1)
    substring_(k - 1, max(0, s - 1), min(sub_len, t - 1), output)

    if s <= 1 + sub_len < t:
        output.append("2")

    substring_(k - 1, max(0, s - sub_len - 2), min(sub_len, t - sub_len - 2), output)

    if s <= 2 * (1 + sub_len) < t:
        output.append("3")


def substring(k, s, t) -> str:
    output: List[str] = []
    substring_(k, s, t, output)
    return "".join(output)


def test(k, s, t) -> bool:
    actual = substring(k, s, t)
    expected = f(k)[s:t]
    return actual == expected


assert test(1, 0, 3)
assert test(2, 2, 6)
assert test(2, 1, 5)
assert test(2, 0, f_len(2))
assert test(3, 0, f_len(3))
assert test(8, 44, 89)
assert test(10, 1001, 2022)
assert test(14, 12345, 45678)
assert test(17, 12345, 112345)
# print(substring(30, 10000, 10100))
print("Tests passed")