在Javascript中遞回檢查包含其他資料的資料

我必須解決一個問題。我有一組以下結構的資料，并且必須創建一個包含閃亮金袋的所有袋子的陣列（包括包含包含閃亮金袋的袋子的袋子）

我已經實作了如下內容，它適用于上述資料集，但不適用于較大的資料集（幾乎 600 行）。我的問題是： - 為什么代碼適用于那個小資料集而不適用于更大的資料集 - 我知道我的不是解決它的最優雅的方法，那么有什么技術可以更有效地解決它？

這是我的代碼

const input = `light red bags contain 1 bright white bag, 2 muted yellow bags.
    dark orange bags contain 3 bright white bags, 4 muted yellow bags.
    bright white bags contain 1 shiny gold bag.
    muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
    shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
    dark olive bags contain 3 faded blue bags, 4 dotted black bags.
    vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
    faded blue bags contain no other bags.
    dotted black bags contain no other bags.`
  .split("\n")
  .map((row) => Array(row))
  .map((row) => row[0].replace("contain", ",").split(","));

function checkColors(arr, str) {
  for (let i = 1; i < arr.length; i  ) {
    if (arr[i].includes(str)) return arr[0];
  }
}

let colors = input
  .map((entry) => checkColors(entry, "shiny gold"))
  .filter((entry) => entry != undefined)
  .map((entry) => entry.replace("bags", "").trim());

let colorsMain = colors;

let tempCol = [];
do {
  for (let j = 0; j < colors.length; j  ) {
    tempCol = input.map((entry) => checkColors(entry, colors[j]));
  }
  tempCol = tempCol
    .filter((entry) => entry != undefined)
    .map((entry) => entry.replace("bags", "").trim());

  colorsMain = colorsMain.concat(tempCol);
  colors = tempCol;
  console.log(colorsMain);
} while (tempCol.length > 0);

console.log(colorsMain.length);

uj5u.com熱心網友回復：

您可以構建一個具有所有關系的物件，然后收集所需的值。

const
    addToSet = (s, v) => (relations[v] || []).reduce(addToSet, s.add(v)),
    data = `light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.`,
    relations = data
        .split(/[\r\n] /)
        .reduce((r, s) => {
            const
                [value, key] = s.split(' bags contain '),
                keys = key === 'no other bags.'
                    ? []
                    : key
                        .split(/[,.]\s*/)
                        .filter(Boolean)
                        .map(s => s.match(/\d \s(.*)\sbag/)[1]);

            keys.forEach(k => (r[k] ??= []).push(value));
            return r;
        }, {}),
    result = [...relations['shiny gold'].reduce(addToSet, new Set)];

console.log(result);
console.log(relations);

.as-console-wrapper { max-height: 100% !important; top: 0; }

uj5u.com熱心網友回復：

這個怎么樣？

const input = `light red bags contain 1 bright white bag, 2 muted yellow bags.
    dark orange bags contain 3 bright white bags, 4 muted yellow bags.
    bright white bags contain 1 shiny gold bag.
    muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
    shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
    dark olive bags contain 3 faded blue bags, 4 dotted black bags.
    vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
    faded blue bags contain no other bags.
    dotted black bags contain no other bags.`

function buildColorDict(input) {
  const colorDict = {}
  input.split("\n").map((line) => {
    return line.match(/([a-zA-Z] \s [a-zA-Z] ) (?=\s bags?)/g)
  }).forEach((arr) => {
    arr.slice(1).forEach((color) => {
      colorDict[color] ? colorDict[color].push(arr[0]) : colorDict[color] = [arr[0]]
    })
  })
  return colorDict
}

function lookUp(colorDict, color) {
  const _lookUp = (_color) => {
    if (colorDict[_color]) {
      return colorDict[_color].concat(colorDict[_color].map((_color1)=> _lookUp(_color1)).flat())
    } else {
      return []
    }
  }
  return new Set(_lookUp(color))
}

const colorDict = buildColorDict(input)
const result = lookUp(colorDict, "shiny gold")

console.log(Array.from(result))

基本上，從inputusing 中提取顏色regex，并構建一個反向查找字典。給定一種顏色，讓我們說shiny gold。它查找包含它的袋子，并使用找到的顏色以遞回方式查找哪些袋子包含找到的彩色袋子。

標籤：javascript 递归

上一篇：高效遞回隨機抽樣

下一篇：中序遍歷-在C語言中將節點資料添加到Int陣列