将对象的数组转换为按值分组的数组的数组

Question

在fabric.js应用程序中，我将元素分为几组。用户可以形成包含任意数量元素的任意数量的组。所附图像显示了分为三组的元素，每个元素显示了其ID。

[当用户完成创建组后，该应用会测量元素之间的距离，并将元素置于“父-子”关系中。这导致对象数组：

var elements = [
    { "parent": 1, "children": [ 2 ] },
    { "parent": 2, "children": [ 1 ] },
    { "parent": 3, "children": [ 7 ] },
    { "parent": 4, "children": [ 5, 6 ] },
    { "parent": 5, "children": [ 4, 6, 7 ] },
    { "parent": 6, "children": [ 4, 5 ] },
    { "parent": 7, "children": [ 3, 5 ] },
    { "parent": 8, "children": [ 9 ] },
    { "parent": 9, "children": [ 8, 11 ] },
    { "parent": 10, "children": [ 11, 12 ] },
    { "parent": 11, "children": [ 9, 10 ] },
    { "parent": 12, "children": [ 10 ] }
];

组中的每个元素都是与其最接近的元素的父元素，但同时也是与其最接近的元素的子元素。在此示例中，如何从“元素”数组中获得包含三个子数组的数组？每个结果子数组应包含仅在该组中的元素的ID。最终结果应为：

var groups = [
    [1, 2],
    [3, 4, 5, 6, 7],
    [8, 9, 10, 11, 12]
];

Answer 1

1）通过遍历元素来构建集。对于每个元素，检查parent是否在任何现有集中。如果没有可用的集合，则创建集合。将孩子添加到集合中。2）现在，我们有了集合的数组，并且可能有相交的集合，需要合并。3）将集合的数组转换为数组的数组。

PS：我认为合并的步骤2可以在步骤1本身中组合。

var elements = [
  { parent: 1, children: [2] },
  { parent: 2, children: [1] },
  { parent: 3, children: [7] },
  { parent: 4, children: [5, 6] },
  { parent: 5, children: [4, 6, 7] },
  { parent: 6, children: [4, 5] },
  { parent: 7, children: [3, 5] },
  { parent: 8, children: [9] },
  { parent: 9, children: [8, 11] },
  { parent: 10, children: [11, 12] },
  { parent: 11, children: [9, 10] },
  { parent: 12, children: [10] }
];

const arrSets = [];

elements.forEach(({ parent, children }) => {
  let set = arrSets.find(set => set.has(parent));
  if (!set) {
    set = new Set();
    set.add(parent);
    arrSets.push(set);
  }
  children.forEach(x => set.add(x));
});

const resSets = [];
arrSets.forEach(set => {
  let curr = resSets.find(dat => [...set].some(x => dat.has(x)));
  if (!curr) {
    curr = new Set();
    resSets.push(curr);
  }
  [...set].forEach(x => curr.add(x));
});

const arr = resSets.map(set => [...set]);

console.log(arr);

Answer 2

这里是使用堆栈解决问题的另一种方法。

• [从父级开始，遍历子级及其子级，直到堆栈为空。这是一组。
• 维护访问数组以避免循环
• 如果不为空，则将组推入主数组

function findGrops(elements) {
  const eleMap = {};
  // build a parent => children map
  elements.forEach( e => {
    eleMap[e.parent] = e.children;
  });

  const groups = [];
  const visited = {};

  // iterate in a depth first way
  // parent -> children -> their children until empty
  Object.keys(eleMap).forEach( k => {
    let grp = [];
    let stk = [k]; //parseInt(k,10) to avoid the quotes
    while( stk.length > 0) {
      let x = stk.pop();
      if (!(x in visited)) {
        grp.push(x);
        visited[x] = true;
        // add children to the stack
        stk = stk.concat(eleMap[x]);
      }
    }
    // push to groups array
    grp.length && groups.push(grp);
  });

  return groups;
}

const input = [
    { "parent": 1, "children": [ 2 ] },
    { "parent": 2, "children": [ 1 ] },
    { "parent": 3, "children": [ 7 ] },
    { "parent": 4, "children": [ 5, 6 ] },
    { "parent": 5, "children": [ 4, 6, 7 ] },
    { "parent": 6, "children": [ 4, 5 ] },
    { "parent": 7, "children": [ 3, 5 ] },
    { "parent": 8, "children": [ 9 ] },
    { "parent": 9, "children": [ 8, 11 ] },
    { "parent": 10, "children": [ 11, 12 ] },
    { "parent": 11, "children": [ 9, 10 ] },
    { "parent": 12, "children": [ 10 ] }
];

  console.log('result:', findGrops(input));