查找避免使用递归函数的子串

Question

我正在研究 Python 中的算法并解决一个问题：

Let x(k) be a recursively defined string with base case x(1) = "123" and x(k) is "1" + x(k-1) + "2" + x(k-1) + "3". Given three positive integers k,s, and t, find the substring x(k)[s:t].

For example, if k = 2, s = 1 and t = 5,x(2) = 112321233 and 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])

虽然我的第一种方法给出了正确的答案，但问题是当k大于20时构建字符串x的时间太长。程序需要在k小于50时在16秒内完成。我试过了使用记忆但它没有帮助，因为我不允许缓存每个测试用例。因此我认为我必须避免使用递归函数来加速程序。有什么我应该考虑的方法吗？

Answer 1

这是一个有趣的问题。我不确定我是否有时间编写代码，但这里概述了如何解决它。注意：请参阅的更好答案。

正如评论中所讨论的，您无法生成实际的字符串：随着 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.

为了便于讨论，我们可以将字符串分为以下几个区域。 start/end 值使用标准 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 2

基于，这里有一些 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")

Answer 3

我们可以看到x(k)表示的字符串的长度随着k的增加呈指数增长：

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

所以：

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

对于k等于100，这相当于长度超过10³⁰。这比人体中的原子还多！

由于参数 s 和 t 将占用（相比之下）一小部分，因此您不需要产生整个字符串。您仍然可以使用递归，但要将 s 和 t 范围传递给每个调用。然后，当您看到该切片实际上位于您要生成的字符串的外部时，您就可以退出而无需更深入地递归，从而节省了 lot时间和（字符串）space.

以下是您的操作方法：

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 4

这是 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);

查找避免使用递归函数的子串

Find the substring avoiding the use of recursive function

python

algorithm

math

recursion

big-o