从列表中获取祖先的对象列表和后代的对象列表

Question

我有一个带有键的 JSON 对象，值是其祖先的有序列表，我想找到一种方法来生成祖先列表和后代列表

输入：

{
"Category 1111": ["Category 1", "Category 11", "Category 111"]
}

输出应该类似于

listAncestors: {
   "Category 1": [],
   "Category 11": ["Category 1"],
   "Category 111": ["Category 1", "Category 11"],
   "Category 1111": ["Category 1", "Category 11", "Category 111"]
}

listDescendants: {
   "Category 1": ["Category 11", "Category 111", "Category 1111"],
   "Category 11": ["Category 111", "Category 1111"],
   "Category 111": ["Category 1111"],
   "Category 1111": []
}

有谁知道我可以遵循的类似已知算法或建议的解决方案

编辑：我的解决方案是：

const getList = () => {
  const newList = Object.keys(input).map((k) => [...input[k], k]);
  const listAns = {};
  const listDes = {};
  newList[0].forEach((k, idx) => {
    listAns[k] = newList.slice(0, idx);
    listDes[k] = newList.slice(idx + 1, newList.length);
  });
};

谢谢

Answer 1

感谢您的编辑。这很有帮助。下次也请解释一下你的代码哪里出了问题。

我认为您的方向是正确的。当然，从现有格式创建 newList 是朝着正确方向迈出的一步。我的实现做同样的事情，代码略有不同。

身材的话，你好像缺了一个档次。输入结构似乎允许多人使用他们的前因链。但是你只和一个一起工作。您还有一个没有输出的函数——通常是一个警告标志——也没有输入——甚至更多。所以这是我如何编写这个版本的一个过程：

const family = (youths) => {
  const chains = Object .entries (youths) .map (([k, v]) => [...v, k])

  return {
    listAncestors: Object .fromEntries (chains .flatMap (
      chain => chain .map ((c, i, a) => [c, a .slice (0, i)])
    )),
    listDescendants: Object .fromEntries (chains .flatMap (
      chain => chain .map ((c, i, a) => [c, a .slice (i + 1)])
    ))
  }
}

console .log (family ({
  "Category 1111": ["Category 1", "Category 11", "Category 111"],
  "Category abc": ["Category a", "Category b"]
}))

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

我的 chains 相当于你的 newList。我找不到一个好听的名字来暗示像家谱的垂直切片。不过感觉还是比newList有意义一点。 chains 的实现与您的类似，但 Object .entries 似乎比 Object .keys + input[k]

更干净

之后，为了获得祖先，我们获取每个链并映射条目，创建一个 two-element 数组，将每个人作为第一个条目，并将链中所有在它之前的人的列表作为它的祖先。然后我们使用 Object.fromEntries 把它变成一个单一的对象。我们对后代做类似的事情，除了我们列出所有在这个人之后的人作为它的后代。

这段代码很好，我们可以很容易地把它留在那里。但是 listAncestors 和 listDescendants 之间确实存在一些重复。考虑到这一点可能会很好。随着重复，二是最难决定的数字。一旦遇到三个非常相似的代码副本，我总是会寻求重构。有两个，我可能会离开它，或者我可能会选择抽象它。我没有任何 hard-and-fast 规则。但让我们看看它会如何发展。

此版本将共性抽象为辅助函数：

const group = (chains, fn) => Object .fromEntries (chains .flatMap (
  chain => chain .map ((c, i, a) => [c, fn (a, i)])
))

const family = (youths) => {
  const chains = Object .entries (youths) .map (([k, v]) => [...v, k])
  
  return {
    listAncestors: group (chains, (a, i) => a .slice (0, i)),
    listDescendants: group (chains, (a, i) => a .slice (i + 1))
  }
}

我们添加了辅助函数 group 并使用它来简化 listAncestors 和 listDescendants 的实现。这并没有真正改变 line-count 或类似的东西，但是这两个函数都比上面的更简单。

我的个人偏好是尽可能避免局部变量，在没有赋值的情况下工作（除了重要的功能）或者实际上根本没有语句，只有表达式。这种偏好的原因对我来说很重要，但不值得花时间在这里。但我可能会进一步重构它，使 chains 成为默认参数，如下所示：

const family = (youths, chains = Object .entries (youths) .map (([k, v]) => [...v, k])) => ({
  listAncestors: group (chains, (a, i) => a .slice (0, i)),
  listDescendants: group (chains, (a, i) => a .slice (i + 1))
})

或者，使用简单的助手，const call = (fn, ...args) => fn (...args)，我可能会这样写：

const family = (youths) => call (
  (chains = Object .entries (youths) .map (([k, v]) => [...v, k])) => ({
    listAncestors: group (chains, (a, i) => a .slice (0, i)),
    listDescendants: group (chains, (a, i) => a .slice (i + 1))
  }))

后者比默认参数更安全，默认参数在某些情况下可能会失败，但如果我能控制函数的调用方式，我会交替使用它们。

从列表中获取祖先的对象列表和后代的对象列表

Get object list of Ancestors and object list of Descendants from a list

javascript

algorithm

json

graph-theory

graph