如何生成包含关键字的字符串？

Question

我目前正在制作一个程序，其中包含许多利用 Math.rand() 的函数。我正在尝试使用给定的关键字（在本例中为车床）生成一个字符串。我希望程序记录一个具有“车床”（或它的任何版本，是否有大写字母）的字符串，但我尝试过的所有程序都达到了它的调用堆栈大小限制（我明白为什么，我想要程序生成一个带有单词的字符串，而不会达到其调用堆栈大小）。

我试过的：

function generateStringWithKeyword(randNum: number) {
  const chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789+/";
  let result = "";
  for(let i = 0; i < randNum; i++) {
    result += chars[Math.floor(Math.random() * chars.length)];
    if(result.includes("lathe")) {
      continue;
    } else {
      generateStringWithKeyword(randNum);
    }
  }
  console.log(result);
}

这就是我现在所拥有的，在对 Whosebug 进行了简短的研究之后，我了解到添加带有 continue 的 if/else 块可能比使用

更好

if(!result.includes("lathe")) return generateStringWithKeyword(randNum);

但这两种方式我都达到了调用堆栈大小限制。

Answer 1

你的算法的“正确”版本，写成迭代函数而不是递归函数，以免超过堆栈深度，看起来像这样：

function generateStringWithKeyword(randNum: number) {
    const chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789+/";
    let result = "";
    let attemptCnt = 0;
    while (!result.toLowerCase().includes("lathe")) {
        attemptCnt++;
        result = "";
        for (let i = 0; i < randNum; i++) {
            result += chars[Math.floor(Math.random() * chars.length)];
        }
        if (attemptCnt > 1e6) {
            console.log("I GIVE UP");
            return;
        }
    }
    console.log(result);
    return result;
}

我不喜欢我的浏览器因为无法完成的脚本而挂起，所以我在其中设置了最大尝试次数。一百万的机会似乎是合理的。当您尝试时，会发生这种情况：

generateStringWithKeyword(10); // I GIVE UP

这是有道理的；让我们进行粗略的粗略概率计算，看看我们预计这需要多长时间。 "lathe" 在某些情况下出现在单词位置 1 的概率是 (2/64)×(2/64)×(2×64)×(2/64)×(2/64) ( “L”或“l”先出现，然后是“A”或“a”等）大约为3×10^-8。对于长度为 10 的单词，"lathe" 可以从位置 1、2、3、4、5 或 6 开始出现。虽然这不完全正确，但让我们将其视为将获得的机会乘以 6某个地方的词，所以得到有效结果的实际机会大约是 1.8×10^-7。因此我们可以预计，您需要获得大约 1 ÷ 1.8×10^-7 = 560 万次成功机会。

哦，该死，我只给了它一百万。让我们将其提高到 1000 万，然后再试一次：

generateStringWithKeyword(10); // "lATHELEYSc"

太棒了！虽然，它有时还是会放弃。事实上，一个需要数百万次尝试才能成功的算法是非常非常低效的。您可能想阅读有关 bogosort 的内容，这是一种排序算法，它通过随机打乱事物并检查它们是否已排序来工作，并且它会不断尝试直到它起作用。它用于教育目的，以强调此类技术的实际性能如何不够实用。没有人愿意真正使用这样的算法。

那么您将如何以“正确”的方式进行操作？好吧，我的建议是第一次就正确地构建你的结果。如果您有 10 个字符，其中 5 个在某些情况下需要 "lathe"，那么您将需要 5 个真正随机的字符。所以随机决定这些字母中有多少应该在 "lathe" 之前。例如，如果您选择 2，则放入 2 个随机字符，在随机情况下加上 "lathe"，再加上 3 个随机字符。

可能是这样的，我主要使用与您相同风格的 for-循环和 += 字符串连接：

function generateStringWithKeyword(randNum: number) {
    const keyword = "lathe";
    if (randNum < keyword.length) throw new Error(
        "This is not possible; \"" + keyword + "\" doesn't fit in " + randNum + " characters"
    );
    const actuallyRandNum = randNum - keyword.length;
    const chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789+/";
    let result = "";
    const kwInsertionPoint = Math.floor(Math.random() * (actuallyRandNum + 1));
    for (let i = 0; i < kwInsertionPoint; i++) {
        result += chars[Math.floor(Math.random() * chars.length)];
    }
    for (let i = 0; i < keyword.length; i++) {
        result += Math.random() < 0.5 ? keyword[i].toLowerCase() : keyword[i].toUpperCase();
    }
    for (let i = kwInsertionPoint; i < actuallyRandNum; i++) {
        result += chars[Math.floor(Math.random() * chars.length)];
    }
    return result;
}

如果你运行这个，你会发现它非常高效，而且永不放弃：

console.log(Array.from({ length: 4 }, () => generateStringWithKeyword(5)).join(" "));
// "lathE LaThe lATHe LatHe"

console.log(Array.from({ length: 4 }, () => generateStringWithKeyword(7)).join(" "));
// "p6lAtHe laThE01 nlaTheK lATHeRJ" 

console.log(Array.from({ length: 4 }, () => generateStringWithKeyword(10)).join(" "));
// "giMqzLaTHe 5klAthegBo oVdLatHe0q twNlATheCr"

Playground link to code

如何生成包含关键字的字符串？

How do I generate a string that contains a keyword?

string

random

keyword

typescript