创建了一个脚本来输出可能的口袋妖怪起始元素替代品（火 -> 草 -> 水）。靠蛮力就成功了，如何高效？
Created a script to output possible Pokemon starter elements alternatives (Fire -> Grass -> Water). Succeeded with brute force, how to be efficient?
这是我的代码：
const fs = require("fs");
const { type } = require("os");
//Functions
const reformat = (types) => {
let map = new Map();
types.forEach((e) => {
let id = e.name;
let val = [e.strengths];
map.set(id, val);
});
return map;
};
const search = (types) => {
let arr = [];
let flags = [];
let count = 0;
types.forEach((strength, type) => {
// console.log(`1: ${type}: ${strength}`);
let a = type;
let b, c;
strength[0].forEach((type_b) => {
let strengths_b = types.get(type_b);
// console.log("2: " + strengths_b);
strengths_b[0].forEach((type_c) => {
let strengths_c = types.get(type_c);
// console.log("3: " + strengths_c);
if (strengths_c[0].includes(a)) {
let b = type_b;
let c = type_c;
console.log(`Found: ${a} => ${b} => ${c}`);
arr.push([a, b, c]);
} else {
}
});
});
});
// console.log(arr);
};
//Procedure
let types = JSON.parse(fs.readFileSync("types.json"));
types = reformat(types);
search(types);
// console.log(types);
这是 JSON 文件：
[
{
"name": "Normal",
"immunes": ["Ghost"],
"weaknesses": ["Rock", "Steel"],
"strengths": []
},
{
"name": "Fire",
"immunes": [],
"weaknesses": ["Fire", "Water", "Rock", "Dragon"],
"strengths": ["Grass", "Ice", "Bug", "Steel"]
},
{
"name": "Water",
"immunes": [],
"weaknesses": ["Water", "Grass", "Dragon"],
"strengths": ["Fire", "Ground", "Rock"]
},
{
"name": "Electric",
"immunes": ["Ground"],
"weaknesses": ["Electric", "Grass", "Dragon"],
"strengths": ["Water", "Flying"]
},
{
"name": "Grass",
"immunes": [],
"weaknesses": [
"Fire",
"Grass",
"Poison",
"Flying",
"Bug",
"Dragon",
"Steel"
],
"strengths": ["Water", "Ground", "Rock"]
},
{
"name": "Ice",
"immunes": [],
"weaknesses": ["Fire", "Water", "Ice", "Steel"],
"strengths": ["Grass", "Ground", "Flying", "Dragon"]
},
{
"name": "Fighting",
"immunes": ["Ghost"],
"weaknesses": ["Poison", "Flying", "Psychic", "Bug", "Fairy"],
"strengths": ["Normal", "Ice", "Rock", "Dark", "Steel"]
},
{
"name": "Poison",
"immunes": ["Steel"],
"weaknesses": ["Poison", "Ground", "Rock", "Ghost"],
"strengths": ["Grass", "Fairy"]
},
{
"name": "Ground",
"immunes": ["Flying"],
"weaknesses": ["Grass", "Bug"],
"strengths": ["Fire", "Electric", "Poison", "Rock", "Steel"]
},
{
"name": "Flying",
"immunes": [],
"weaknesses": ["Electric", "Rock", "Steel"],
"strengths": ["Grass", "Fighting", "Bug"]
},
{
"name": "Psychic",
"immunes": ["Dark"],
"weaknesses": ["Psychic", "Steel"],
"strengths": ["Fighting", "Poison"]
},
{
"name": "Bug",
"immunes": [],
"weaknesses": [
"Fire",
"Fighting",
"Poison",
"Flying",
"Ghost",
"Steel",
"Fairy"
],
"strengths": ["Grass", "Psychic", "Dark"]
},
{
"name": "Rock",
"immunes": [],
"weaknesses": ["Fighting", "Ground", "Steel"],
"strengths": ["Fire", "Ice", "Flying", "Bug"]
},
{
"name": "Ghost",
"immunes": ["Normal"],
"weaknesses": ["Dark"],
"strengths": ["Psychic", "Ghost"]
},
{
"name": "Dragon",
"immunes": ["Fairy"],
"weaknesses": ["Steel"],
"strengths": ["Dragon"]
},
{
"name": "Dark",
"immunes": [],
"weaknesses": ["Fighting", "Dark", "Fairy"],
"strengths": ["Psychic", "Ghost"]
},
{
"name": "Steel",
"immunes": [],
"weaknesses": ["Fire", "Water", "Electric", "Steel"],
"strengths": ["Ice", "Rock", "Fairy"]
},
{
"name": "Fairy",
"immunes": [],
"weaknesses": ["Fire", "Poison", "Steel"],
"strengths": ["Fighting", "Dragon", "Dark"]
}
]
这是输出：
Found: Fire => Grass => Water
Found: Fire => Grass => Ground
Found: Fire => Grass => Rock
Found: Fire => Ice => Ground
Found: Fire => Steel => Rock
Found: Water => Fire => Grass
Found: Water => Ground => Electric
Found: Electric => Water => Ground
Found: Grass => Water => Fire
Found: Grass => Ground => Fire
Found: Grass => Ground => Poison
Found: Grass => Rock => Fire
Found: Grass => Rock => Ice
Found: Grass => Rock => Flying
Found: Grass => Rock => Bug
Found: Ice => Grass => Rock
Found: Ice => Ground => Fire
Found: Ice => Ground => Rock
Found: Ice => Ground => Steel
Found: Ice => Flying => Fighting
Found: Fighting => Ice => Flying
Found: Fighting => Rock => Flying
Found: Fighting => Dark => Psychic
Found: Fighting => Steel => Fairy
Found: Poison => Grass => Ground
Found: Ground => Fire => Grass
Found: Ground => Fire => Ice
Found: Ground => Electric => Water
Found: Ground => Poison => Grass
Found: Ground => Rock => Ice
Found: Ground => Steel => Ice
Found: Flying => Grass => Rock
Found: Flying => Fighting => Ice
Found: Flying => Fighting => Rock
Found: Psychic => Fighting => Dark
Found: Bug => Grass => Rock
Found: Rock => Fire => Grass
Found: Rock => Fire => Steel
Found: Rock => Ice => Grass
Found: Rock => Ice => Ground
Found: Rock => Flying => Grass
Found: Rock => Flying => Fighting
Found: Rock => Bug => Grass
Found: Ghost => Ghost => Ghost
Found: Dragon => Dragon => Dragon
Found: Dark => Psychic => Fighting
Found: Steel => Ice => Ground
Found: Steel => Rock => Fire
Found: Steel => Fairy => Fighting
Found: Fairy => Fighting => Steel
正如您所注意到的，类似的结果被打印了多次（例如 Fire/Grass/Water 每个元素被打印了 3 次）。
此外，该算法是超级暴力算法，三个循环相互堆叠（我假设这会使它成为 O(n^3)？）。我记得看到过与此类似的问题（不是口袋妖怪，而是类似的结构等），但我不记得或想不出什么是最好的解决这个问题的方法，而不是通过暴力和迭代现有的处理能力来浪费处理能力元素链。我尝试使用 Map 和所有这些但似乎没有任何效果。这是我的第一个 Whosebug post 如果我把其中的一些写错了，请原谅我！
我不确定是否可以降低初始查询的复杂性（其他人，请证明我错了:)）
但是，由于所有结果都是静态的（弱点和优势不会改变），您可以使用蛮力方法计算所有内容并将结果存储在平面对象或 json 文件中。从那时起，查找将是 O(1).
根据您想要的信息，您可以采用如下格式：
alternatives = {
fire: ['Grass Water', 'Grass Ground', 'Grass Rock', 'Ice Ground', 'Steel Rock'],
water: ['Fire Grass', 'Ground Electric'],
..
}
祝你好运
This is my first Whosebug post so pardon me if I put some of these wrong!
其实，这已经是well-done第一次post了。荣誉！
但是我有两点建议：
您可能应该对问题进行更多描述。您的工作源代码很棒，但我敢肯定我不是唯一一个对口袋妖怪一无所知的人，因此没有问题的背景。我不知道“入门集”是什么，或者您的标题和输出中的箭头代表什么（也许什么都不知道。）
您可以阅读How do I create a runnable stack snippet? so that readers can see the result right in their browsers. (You can edit post 随时添加一个。）
现在回到问题本身。
您担心性能。您是否测试过它还不够快？如果以上是数据的范围，那么我预计这不会花费超过几毫秒的时间来处理。那太长了吗？还是真实数据要大得多？如果它更大，你能不能不按照 Zac Butko 的建议做 运行 静态地作为构建步骤，将结果存储在文件中，或者在应用程序初始化期间，在应用程序的生命周期内将其存储在内存中？
我没有任何可以加快速度的建议。在我看来，您必须访问数据中的所有 O (n ^ 3) 路径，因此存在一个严格的算法下限。 （我以前在这方面错了，也许我在这里，但我不确定如何做到这一点。）
但我确实有我认为更简洁的代码来做同样的事情。第一遍创建与您发现的相同的输出，可能如下所示：
const paths = (types, length, children = Object .keys (types)) =>
length <= 1
? children .map (s => [s])
: children .flatMap (s => paths (types, length - 1, types [s]) .map (p => [s, ...p]))
const search = (ts, types = Object .fromEntries (ts .map ((t) => [t .name, t .strengths]))) =>
paths (types, 3) .filter ((s) => types [s [s .length - 1]] .includes (s [0]))
const types = [{name: "Normal", immunes: ["Ghost"], weaknesses: ["Rock", "Steel"], strengths: []}, {name: "Fire", immunes: [], weaknesses: ["Fire", "Water", "Rock", "Dragon"], strengths: ["Grass", "Ice", "Bug", "Steel"]}, {name: "Water", immunes: [], weaknesses: ["Water", "Grass", "Dragon"], strengths: ["Fire", "Ground", "Rock"]}, {name: "Electric", immunes: ["Ground"], weaknesses: ["Electric", "Grass", "Dragon"], strengths: ["Water", "Flying"]}, {name: "Grass", immunes: [], weaknesses: ["Fire", "Grass", "Poison", "Flying", "Bug", "Dragon", "Steel"], strengths: ["Water", "Ground", "Rock"]}, {name: "Ice", immunes: [], weaknesses: ["Fire", "Water", "Ice", "Steel"], strengths: ["Grass", "Ground", "Flying", "Dragon"]}, {name: "Fighting", immunes: ["Ghost"], weaknesses: ["Poison", "Flying", "Psychic", "Bug", "Fairy"], strengths: ["Normal", "Ice", "Rock", "Dark", "Steel"]}, {name: "Poison", immunes: ["Steel"], weaknesses: ["Poison", "Ground", "Rock", "Ghost"], strengths: ["Grass", "Fairy"]}, {name: "Ground", immunes: ["Flying"], weaknesses: ["Grass", "Bug"], strengths: ["Fire", "Electric", "Poison", "Rock", "Steel"]}, {name: "Flying", immunes: [], weaknesses: ["Electric", "Rock", "Steel"], strengths: ["Grass", "Fighting", "Bug"]}, {name: "Psychic", immunes: ["Dark"], weaknesses: ["Psychic", "Steel"], strengths: ["Fighting", "Poison"]}, {name: "Bug", immunes: [], weaknesses: ["Fire", "Fighting", "Poison", "Flying", "Ghost", "Steel", "Fairy"], strengths: ["Grass", "Psychic", "Dark"]}, {name: "Rock", immunes: [], weaknesses: ["Fighting", "Ground", "Steel"], strengths: ["Fire", "Ice", "Flying", "Bug"]}, {name: "Ghost", immunes: ["Normal"], weaknesses: ["Dark"], strengths: ["Psychic", "Ghost"]}, {name: "Dragon", immunes: ["Fairy"], weaknesses: ["Steel"], strengths: ["Dragon"]}, {name: "Dark", immunes: [], weaknesses: ["Fighting", "Dark", "Fairy"], strengths: ["Psychic", "Ghost"]}, {name: "Steel", immunes: [], weaknesses: ["Fire", "Water", "Electric", "Steel"], strengths: ["Ice", "Rock", "Fairy"]}, {name: "Fairy", immunes: [], weaknesses: ["Fire", "Poison", "Steel"], strengths: ["Fighting", "Dragon", "Dark"]}]
console .log (search (types))
.as-console-wrapper {max-height: 100% !important; top: 0}
paths 采用类似于 {a: ['b', 'c'], b: ['d', 'e'], c: ['e'], d: ['b', 'c'], e: ['a', 'b']} 的结构以及路径长度，比如 3，return 包含所有长度为 3 的路径，我们可以描述作为 abd、abe、ace、bdb、bdc、bea、beb、cea、ceb、dbd、dbe、dce、eab、eac、ebd 和 ebe。
search 获取您的输入，使用 strengths 属性将其重新配置为上述格式，然后对结果调用 paths，长度为 3。然后它过滤以仅包含将从最终元素循环回初始元素的那些路径。
这为您提供了生成的答案，但您想删除重复项，说其中许多重复出现了 3 次。你的符号有点混乱，输出像 Found: Rock => Fire => Grass。这些箭头让我假设这是一个有序的 collection。但是从上面来看，我认为你想把它们当作无序的集合，并且只有 return 其中之一。如果是这种情况，我们可以事后过滤以删除它们，代码如下：
const dedupe = (fn) => (xs, res = new Set()) => xs .filter (
(x, _, __, key = fn (x), dup = res .has (key)) => ((res .add (key)), ! dup)
)
const search = (ts, types = Object .fromEntries (ts .map ((t) => [t .name, t .strengths]))) =>
dedupe
(s => [... s] .sort () .join ('|'))
(paths (types, 3) .filter ((s) => types [s [s .length - 1]] .includes (s [0])))
这里 dedupe 接受一个函数，该函数为我们的每个 three-element 集合找到一个一致的字符串键。它 return 是一个函数，它接受一个数组并保留那些在传递给该函数时生成未使用的密钥的数组。
我们通过调用 dedupe 来结束搜索中的输出，向其传递一个函数，该函数对元素进行排序并将它们连接到一个新的字符串中，并散布一个分隔符。 （如果“|”字符可能出现在您的数据中，那么我会选择不同的分隔符，但即使您不这样做，唯一可能的失败案例也很模糊。）例如，当您点击 ['Water', 'Ground', 'Electric']，它将排序并连接到键 "Electric|Ground|Water" 中，并将其存储在其集合中。然后当我们看到 ['Electric', 'Water', 'Ground'] 时它也会生成相同的键，所以这个数组不包括在内。
你可以通过展开这个片段来完全看到它：
const paths = (types, length, children = Object .keys (types)) =>
length <= 1
? children .map (s => [s])
: children .flatMap (s => paths (types, length - 1, types [s]) .map (p => [s, ...p]))
const dedupe = (fn) => (xs, res = new Set()) => xs .filter (
(x, _, __, key = fn (x), dup = res .has (key)) => ((res .add (key)), ! dup)
)
const search = (ts, types = Object .fromEntries (ts .map ((t) => [t .name, t .strengths]))) =>
dedupe
(s => [... s] .sort () .join ('|'))
(paths (types, 3) .filter ((s) => types [s [s .length - 1]] .includes (s [0])))
const types = [{name: "Normal", immunes: ["Ghost"], weaknesses: ["Rock", "Steel"], strengths: []}, {name: "Fire", immunes: [], weaknesses: ["Fire", "Water", "Rock", "Dragon"], strengths: ["Grass", "Ice", "Bug", "Steel"]}, {name: "Water", immunes: [], weaknesses: ["Water", "Grass", "Dragon"], strengths: ["Fire", "Ground", "Rock"]}, {name: "Electric", immunes: ["Ground"], weaknesses: ["Electric", "Grass", "Dragon"], strengths: ["Water", "Flying"]}, {name: "Grass", immunes: [], weaknesses: ["Fire", "Grass", "Poison", "Flying", "Bug", "Dragon", "Steel"], strengths: ["Water", "Ground", "Rock"]}, {name: "Ice", immunes: [], weaknesses: ["Fire", "Water", "Ice", "Steel"], strengths: ["Grass", "Ground", "Flying", "Dragon"]}, {name: "Fighting", immunes: ["Ghost"], weaknesses: ["Poison", "Flying", "Psychic", "Bug", "Fairy"], strengths: ["Normal", "Ice", "Rock", "Dark", "Steel"]}, {name: "Poison", immunes: ["Steel"], weaknesses: ["Poison", "Ground", "Rock", "Ghost"], strengths: ["Grass", "Fairy"]}, {name: "Ground", immunes: ["Flying"], weaknesses: ["Grass", "Bug"], strengths: ["Fire", "Electric", "Poison", "Rock", "Steel"]}, {name: "Flying", immunes: [], weaknesses: ["Electric", "Rock", "Steel"], strengths: ["Grass", "Fighting", "Bug"]}, {name: "Psychic", immunes: ["Dark"], weaknesses: ["Psychic", "Steel"], strengths: ["Fighting", "Poison"]}, {name: "Bug", immunes: [], weaknesses: ["Fire", "Fighting", "Poison", "Flying", "Ghost", "Steel", "Fairy"], strengths: ["Grass", "Psychic", "Dark"]}, {name: "Rock", immunes: [], weaknesses: ["Fighting", "Ground", "Steel"], strengths: ["Fire", "Ice", "Flying", "Bug"]}, {name: "Ghost", immunes: ["Normal"], weaknesses: ["Dark"], strengths: ["Psychic", "Ghost"]}, {name: "Dragon", immunes: ["Fairy"], weaknesses: ["Steel"], strengths: ["Dragon"]}, {name: "Dark", immunes: [], weaknesses: ["Fighting", "Dark", "Fairy"], strengths: ["Psychic", "Ghost"]}, {name: "Steel", immunes: [], weaknesses: ["Fire", "Water", "Electric", "Steel"], strengths: ["Ice", "Rock", "Fairy"]}, {name: "Fairy", immunes: [], weaknesses: ["Fire", "Poison", "Steel"], strengths: ["Fighting", "Dragon", "Dark"]}]
console .log (search (types))
.as-console-wrapper {max-height: 100% !important; top: 0}
这是我的代码：
const fs = require("fs");
const { type } = require("os");
//Functions
const reformat = (types) => {
let map = new Map();
types.forEach((e) => {
let id = e.name;
let val = [e.strengths];
map.set(id, val);
});
return map;
};
const search = (types) => {
let arr = [];
let flags = [];
let count = 0;
types.forEach((strength, type) => {
// console.log(`1: ${type}: ${strength}`);
let a = type;
let b, c;
strength[0].forEach((type_b) => {
let strengths_b = types.get(type_b);
// console.log("2: " + strengths_b);
strengths_b[0].forEach((type_c) => {
let strengths_c = types.get(type_c);
// console.log("3: " + strengths_c);
if (strengths_c[0].includes(a)) {
let b = type_b;
let c = type_c;
console.log(`Found: ${a} => ${b} => ${c}`);
arr.push([a, b, c]);
} else {
}
});
});
});
// console.log(arr);
};
//Procedure
let types = JSON.parse(fs.readFileSync("types.json"));
types = reformat(types);
search(types);
// console.log(types);
这是 JSON 文件：
[
{
"name": "Normal",
"immunes": ["Ghost"],
"weaknesses": ["Rock", "Steel"],
"strengths": []
},
{
"name": "Fire",
"immunes": [],
"weaknesses": ["Fire", "Water", "Rock", "Dragon"],
"strengths": ["Grass", "Ice", "Bug", "Steel"]
},
{
"name": "Water",
"immunes": [],
"weaknesses": ["Water", "Grass", "Dragon"],
"strengths": ["Fire", "Ground", "Rock"]
},
{
"name": "Electric",
"immunes": ["Ground"],
"weaknesses": ["Electric", "Grass", "Dragon"],
"strengths": ["Water", "Flying"]
},
{
"name": "Grass",
"immunes": [],
"weaknesses": [
"Fire",
"Grass",
"Poison",
"Flying",
"Bug",
"Dragon",
"Steel"
],
"strengths": ["Water", "Ground", "Rock"]
},
{
"name": "Ice",
"immunes": [],
"weaknesses": ["Fire", "Water", "Ice", "Steel"],
"strengths": ["Grass", "Ground", "Flying", "Dragon"]
},
{
"name": "Fighting",
"immunes": ["Ghost"],
"weaknesses": ["Poison", "Flying", "Psychic", "Bug", "Fairy"],
"strengths": ["Normal", "Ice", "Rock", "Dark", "Steel"]
},
{
"name": "Poison",
"immunes": ["Steel"],
"weaknesses": ["Poison", "Ground", "Rock", "Ghost"],
"strengths": ["Grass", "Fairy"]
},
{
"name": "Ground",
"immunes": ["Flying"],
"weaknesses": ["Grass", "Bug"],
"strengths": ["Fire", "Electric", "Poison", "Rock", "Steel"]
},
{
"name": "Flying",
"immunes": [],
"weaknesses": ["Electric", "Rock", "Steel"],
"strengths": ["Grass", "Fighting", "Bug"]
},
{
"name": "Psychic",
"immunes": ["Dark"],
"weaknesses": ["Psychic", "Steel"],
"strengths": ["Fighting", "Poison"]
},
{
"name": "Bug",
"immunes": [],
"weaknesses": [
"Fire",
"Fighting",
"Poison",
"Flying",
"Ghost",
"Steel",
"Fairy"
],
"strengths": ["Grass", "Psychic", "Dark"]
},
{
"name": "Rock",
"immunes": [],
"weaknesses": ["Fighting", "Ground", "Steel"],
"strengths": ["Fire", "Ice", "Flying", "Bug"]
},
{
"name": "Ghost",
"immunes": ["Normal"],
"weaknesses": ["Dark"],
"strengths": ["Psychic", "Ghost"]
},
{
"name": "Dragon",
"immunes": ["Fairy"],
"weaknesses": ["Steel"],
"strengths": ["Dragon"]
},
{
"name": "Dark",
"immunes": [],
"weaknesses": ["Fighting", "Dark", "Fairy"],
"strengths": ["Psychic", "Ghost"]
},
{
"name": "Steel",
"immunes": [],
"weaknesses": ["Fire", "Water", "Electric", "Steel"],
"strengths": ["Ice", "Rock", "Fairy"]
},
{
"name": "Fairy",
"immunes": [],
"weaknesses": ["Fire", "Poison", "Steel"],
"strengths": ["Fighting", "Dragon", "Dark"]
}
]
这是输出：
Found: Fire => Grass => Water
Found: Fire => Grass => Ground
Found: Fire => Grass => Rock
Found: Fire => Ice => Ground
Found: Fire => Steel => Rock
Found: Water => Fire => Grass
Found: Water => Ground => Electric
Found: Electric => Water => Ground
Found: Grass => Water => Fire
Found: Grass => Ground => Fire
Found: Grass => Ground => Poison
Found: Grass => Rock => Fire
Found: Grass => Rock => Ice
Found: Grass => Rock => Flying
Found: Grass => Rock => Bug
Found: Ice => Grass => Rock
Found: Ice => Ground => Fire
Found: Ice => Ground => Rock
Found: Ice => Ground => Steel
Found: Ice => Flying => Fighting
Found: Fighting => Ice => Flying
Found: Fighting => Rock => Flying
Found: Fighting => Dark => Psychic
Found: Fighting => Steel => Fairy
Found: Poison => Grass => Ground
Found: Ground => Fire => Grass
Found: Ground => Fire => Ice
Found: Ground => Electric => Water
Found: Ground => Poison => Grass
Found: Ground => Rock => Ice
Found: Ground => Steel => Ice
Found: Flying => Grass => Rock
Found: Flying => Fighting => Ice
Found: Flying => Fighting => Rock
Found: Psychic => Fighting => Dark
Found: Bug => Grass => Rock
Found: Rock => Fire => Grass
Found: Rock => Fire => Steel
Found: Rock => Ice => Grass
Found: Rock => Ice => Ground
Found: Rock => Flying => Grass
Found: Rock => Flying => Fighting
Found: Rock => Bug => Grass
Found: Ghost => Ghost => Ghost
Found: Dragon => Dragon => Dragon
Found: Dark => Psychic => Fighting
Found: Steel => Ice => Ground
Found: Steel => Rock => Fire
Found: Steel => Fairy => Fighting
Found: Fairy => Fighting => Steel
正如您所注意到的，类似的结果被打印了多次（例如 Fire/Grass/Water 每个元素被打印了 3 次）。
此外，该算法是超级暴力算法，三个循环相互堆叠（我假设这会使它成为 O(n^3)？）。我记得看到过与此类似的问题（不是口袋妖怪，而是类似的结构等），但我不记得或想不出什么是最好的解决这个问题的方法，而不是通过暴力和迭代现有的处理能力来浪费处理能力元素链。我尝试使用 Map 和所有这些但似乎没有任何效果。这是我的第一个 Whosebug post 如果我把其中的一些写错了，请原谅我！
我不确定是否可以降低初始查询的复杂性（其他人，请证明我错了:)）
但是，由于所有结果都是静态的（弱点和优势不会改变），您可以使用蛮力方法计算所有内容并将结果存储在平面对象或 json 文件中。从那时起，查找将是 O(1).
根据您想要的信息，您可以采用如下格式：
alternatives = {
fire: ['Grass Water', 'Grass Ground', 'Grass Rock', 'Ice Ground', 'Steel Rock'],
water: ['Fire Grass', 'Ground Electric'],
..
}
祝你好运
This is my first Whosebug post so pardon me if I put some of these wrong!
其实，这已经是well-done第一次post了。荣誉！
但是我有两点建议：
您可能应该对问题进行更多描述。您的工作源代码很棒，但我敢肯定我不是唯一一个对口袋妖怪一无所知的人，因此没有问题的背景。我不知道“入门集”是什么，或者您的标题和输出中的箭头代表什么（也许什么都不知道。）
您可以阅读How do I create a runnable stack snippet? so that readers can see the result right in their browsers. (You can edit post 随时添加一个。）
现在回到问题本身。
您担心性能。您是否测试过它还不够快？如果以上是数据的范围，那么我预计这不会花费超过几毫秒的时间来处理。那太长了吗？还是真实数据要大得多？如果它更大，你能不能不按照 Zac Butko 的建议做 运行 静态地作为构建步骤，将结果存储在文件中，或者在应用程序初始化期间，在应用程序的生命周期内将其存储在内存中？
我没有任何可以加快速度的建议。在我看来，您必须访问数据中的所有 O (n ^ 3) 路径，因此存在一个严格的算法下限。 （我以前在这方面错了，也许我在这里，但我不确定如何做到这一点。）
但我确实有我认为更简洁的代码来做同样的事情。第一遍创建与您发现的相同的输出，可能如下所示：
const paths = (types, length, children = Object .keys (types)) =>
length <= 1
? children .map (s => [s])
: children .flatMap (s => paths (types, length - 1, types [s]) .map (p => [s, ...p]))
const search = (ts, types = Object .fromEntries (ts .map ((t) => [t .name, t .strengths]))) =>
paths (types, 3) .filter ((s) => types [s [s .length - 1]] .includes (s [0]))
const types = [{name: "Normal", immunes: ["Ghost"], weaknesses: ["Rock", "Steel"], strengths: []}, {name: "Fire", immunes: [], weaknesses: ["Fire", "Water", "Rock", "Dragon"], strengths: ["Grass", "Ice", "Bug", "Steel"]}, {name: "Water", immunes: [], weaknesses: ["Water", "Grass", "Dragon"], strengths: ["Fire", "Ground", "Rock"]}, {name: "Electric", immunes: ["Ground"], weaknesses: ["Electric", "Grass", "Dragon"], strengths: ["Water", "Flying"]}, {name: "Grass", immunes: [], weaknesses: ["Fire", "Grass", "Poison", "Flying", "Bug", "Dragon", "Steel"], strengths: ["Water", "Ground", "Rock"]}, {name: "Ice", immunes: [], weaknesses: ["Fire", "Water", "Ice", "Steel"], strengths: ["Grass", "Ground", "Flying", "Dragon"]}, {name: "Fighting", immunes: ["Ghost"], weaknesses: ["Poison", "Flying", "Psychic", "Bug", "Fairy"], strengths: ["Normal", "Ice", "Rock", "Dark", "Steel"]}, {name: "Poison", immunes: ["Steel"], weaknesses: ["Poison", "Ground", "Rock", "Ghost"], strengths: ["Grass", "Fairy"]}, {name: "Ground", immunes: ["Flying"], weaknesses: ["Grass", "Bug"], strengths: ["Fire", "Electric", "Poison", "Rock", "Steel"]}, {name: "Flying", immunes: [], weaknesses: ["Electric", "Rock", "Steel"], strengths: ["Grass", "Fighting", "Bug"]}, {name: "Psychic", immunes: ["Dark"], weaknesses: ["Psychic", "Steel"], strengths: ["Fighting", "Poison"]}, {name: "Bug", immunes: [], weaknesses: ["Fire", "Fighting", "Poison", "Flying", "Ghost", "Steel", "Fairy"], strengths: ["Grass", "Psychic", "Dark"]}, {name: "Rock", immunes: [], weaknesses: ["Fighting", "Ground", "Steel"], strengths: ["Fire", "Ice", "Flying", "Bug"]}, {name: "Ghost", immunes: ["Normal"], weaknesses: ["Dark"], strengths: ["Psychic", "Ghost"]}, {name: "Dragon", immunes: ["Fairy"], weaknesses: ["Steel"], strengths: ["Dragon"]}, {name: "Dark", immunes: [], weaknesses: ["Fighting", "Dark", "Fairy"], strengths: ["Psychic", "Ghost"]}, {name: "Steel", immunes: [], weaknesses: ["Fire", "Water", "Electric", "Steel"], strengths: ["Ice", "Rock", "Fairy"]}, {name: "Fairy", immunes: [], weaknesses: ["Fire", "Poison", "Steel"], strengths: ["Fighting", "Dragon", "Dark"]}]
console .log (search (types))
.as-console-wrapper {max-height: 100% !important; top: 0}
paths 采用类似于 {a: ['b', 'c'], b: ['d', 'e'], c: ['e'], d: ['b', 'c'], e: ['a', 'b']} 的结构以及路径长度，比如 3，return 包含所有长度为 3 的路径，我们可以描述作为 abd、abe、ace、bdb、bdc、bea、beb、cea、ceb、dbd、dbe、dce、eab、eac、ebd 和 ebe。
search 获取您的输入，使用 strengths 属性将其重新配置为上述格式，然后对结果调用 paths，长度为 3。然后它过滤以仅包含将从最终元素循环回初始元素的那些路径。
这为您提供了生成的答案，但您想删除重复项，说其中许多重复出现了 3 次。你的符号有点混乱，输出像 Found: Rock => Fire => Grass。这些箭头让我假设这是一个有序的 collection。但是从上面来看，我认为你想把它们当作无序的集合，并且只有 return 其中之一。如果是这种情况，我们可以事后过滤以删除它们，代码如下：
const dedupe = (fn) => (xs, res = new Set()) => xs .filter (
(x, _, __, key = fn (x), dup = res .has (key)) => ((res .add (key)), ! dup)
)
const search = (ts, types = Object .fromEntries (ts .map ((t) => [t .name, t .strengths]))) =>
dedupe
(s => [... s] .sort () .join ('|'))
(paths (types, 3) .filter ((s) => types [s [s .length - 1]] .includes (s [0])))
这里 dedupe 接受一个函数，该函数为我们的每个 three-element 集合找到一个一致的字符串键。它 return 是一个函数，它接受一个数组并保留那些在传递给该函数时生成未使用的密钥的数组。
我们通过调用 dedupe 来结束搜索中的输出，向其传递一个函数，该函数对元素进行排序并将它们连接到一个新的字符串中，并散布一个分隔符。 （如果“|”字符可能出现在您的数据中，那么我会选择不同的分隔符，但即使您不这样做，唯一可能的失败案例也很模糊。）例如，当您点击 ['Water', 'Ground', 'Electric']，它将排序并连接到键 "Electric|Ground|Water" 中，并将其存储在其集合中。然后当我们看到 ['Electric', 'Water', 'Ground'] 时它也会生成相同的键，所以这个数组不包括在内。
你可以通过展开这个片段来完全看到它：
const paths = (types, length, children = Object .keys (types)) =>
length <= 1
? children .map (s => [s])
: children .flatMap (s => paths (types, length - 1, types [s]) .map (p => [s, ...p]))
const dedupe = (fn) => (xs, res = new Set()) => xs .filter (
(x, _, __, key = fn (x), dup = res .has (key)) => ((res .add (key)), ! dup)
)
const search = (ts, types = Object .fromEntries (ts .map ((t) => [t .name, t .strengths]))) =>
dedupe
(s => [... s] .sort () .join ('|'))
(paths (types, 3) .filter ((s) => types [s [s .length - 1]] .includes (s [0])))
const types = [{name: "Normal", immunes: ["Ghost"], weaknesses: ["Rock", "Steel"], strengths: []}, {name: "Fire", immunes: [], weaknesses: ["Fire", "Water", "Rock", "Dragon"], strengths: ["Grass", "Ice", "Bug", "Steel"]}, {name: "Water", immunes: [], weaknesses: ["Water", "Grass", "Dragon"], strengths: ["Fire", "Ground", "Rock"]}, {name: "Electric", immunes: ["Ground"], weaknesses: ["Electric", "Grass", "Dragon"], strengths: ["Water", "Flying"]}, {name: "Grass", immunes: [], weaknesses: ["Fire", "Grass", "Poison", "Flying", "Bug", "Dragon", "Steel"], strengths: ["Water", "Ground", "Rock"]}, {name: "Ice", immunes: [], weaknesses: ["Fire", "Water", "Ice", "Steel"], strengths: ["Grass", "Ground", "Flying", "Dragon"]}, {name: "Fighting", immunes: ["Ghost"], weaknesses: ["Poison", "Flying", "Psychic", "Bug", "Fairy"], strengths: ["Normal", "Ice", "Rock", "Dark", "Steel"]}, {name: "Poison", immunes: ["Steel"], weaknesses: ["Poison", "Ground", "Rock", "Ghost"], strengths: ["Grass", "Fairy"]}, {name: "Ground", immunes: ["Flying"], weaknesses: ["Grass", "Bug"], strengths: ["Fire", "Electric", "Poison", "Rock", "Steel"]}, {name: "Flying", immunes: [], weaknesses: ["Electric", "Rock", "Steel"], strengths: ["Grass", "Fighting", "Bug"]}, {name: "Psychic", immunes: ["Dark"], weaknesses: ["Psychic", "Steel"], strengths: ["Fighting", "Poison"]}, {name: "Bug", immunes: [], weaknesses: ["Fire", "Fighting", "Poison", "Flying", "Ghost", "Steel", "Fairy"], strengths: ["Grass", "Psychic", "Dark"]}, {name: "Rock", immunes: [], weaknesses: ["Fighting", "Ground", "Steel"], strengths: ["Fire", "Ice", "Flying", "Bug"]}, {name: "Ghost", immunes: ["Normal"], weaknesses: ["Dark"], strengths: ["Psychic", "Ghost"]}, {name: "Dragon", immunes: ["Fairy"], weaknesses: ["Steel"], strengths: ["Dragon"]}, {name: "Dark", immunes: [], weaknesses: ["Fighting", "Dark", "Fairy"], strengths: ["Psychic", "Ghost"]}, {name: "Steel", immunes: [], weaknesses: ["Fire", "Water", "Electric", "Steel"], strengths: ["Ice", "Rock", "Fairy"]}, {name: "Fairy", immunes: [], weaknesses: ["Fire", "Poison", "Steel"], strengths: ["Fighting", "Dragon", "Dark"]}]
console .log (search (types))
.as-console-wrapper {max-height: 100% !important; top: 0}