javascript - 按每个数组中包含的元素对数组数组进行排序

Question

我需要遍历图中所有连接的组件。 图的路径存储在这样的数组中:

var paths = [
  [5,6],
  [1,2],
  [4,7,5,6],
  [6]
]

在这里我看到 paths[2]=[4,7,5,6] 依赖于 paths[0]=[5,6]取决于 paths[3]=[6]。

现在，我需要递归遍历所有路径来检查哪个包含在另一个路径中，然后首先处理可能有助于解决另一个的路径，即我需要检查哪些数组包含在其他一些数组中:

例子:

process [6]
process [5,6]
process [4,7,5,6]
process [1,2]

由于元素量大，我宁愿不使用递归。 有没有一种方法可以根据每个其他数组中包含的一个数组中的元素对这个数组列表进行排序，以便我可以通过迭代处理它们？

编辑: 我认为这可以通过为每条路径分配权重来解决，如下所示: 每条路径中包含的节点的总和乘以该节点在其他路径中包含的次数，然后按长度升序和权重降序对路径进行排序 - 但这只是我的猜测......

Answer 1

我想...如果我没理解错的话，你是在依赖排序之后。那么我相信完成这项工作的可能方法如下。这是我本可以想出的一种方法，但也可能有更简单的解决方案。

我们必须将相互依赖的连续项目组成组(例如 [6]、[5,6] 和 [4,7 ,5,6]) 然后我们将根据它们的依赖关系对它们进行排序。我猜想在不同的组之间进行排序是没有必要的，因为它们的项目不相关(即 [1,2] 可以出现在带有 [6] 的排序组之前或之后，[5,6] 和 [4,7,5,6])。

var paths = [
             [5,6],
             [1,2],
             [4,7,5,6],
             [6]
            ],
      lut = paths.reduce((table,path,i) => (path.forEach(n => table[n] = table[n] ? table[n].concat([[i,path.length]])
                                                                                            .sort((a,b) => a[1]-b[1])
                                                                                  : [[i,path.length]]),
                                            table),{}),
   sorted = Object.keys(lut).sort((a,b) => lut[b].length - lut[a].length)
                            .reduce((si,k) => (lut[k].forEach(e => !si.includes(e[0]) && si.push(e[0])),si) ,[])
                            .map(idx => paths[idx]);
console.log(sorted);

好的，我们首先从对象 (lut) 之类的查找表开始，在这种特殊情况下，它的形式类似于

{ '1': [ [ 1, 2 ] ],
  '2': [ [ 1, 2 ] ],
  '4': [ [ 2, 4 ] ],
  '5': [ [ 0, 2 ], [ 2, 4 ] ],
  '6': [ [ 3, 1 ], [ 0, 2 ], [ 2, 4 ] ],
  '7': [ [ 2, 4 ] ] 
}

所以我们现在知道路径 6 具有最多的依赖性。 '6': [ [ 3, 1 ], [ 0, 2 ], [ 2, 4 ] ],表示在paths[3]处是单独的；在 paths[0] 它有一个依赖项，在 paths[2] 它有 3 个依赖项。所以我们根据 o 受抚养人的数量进行排序 (.sort((a,b) => a[1]-b[1]))。 一旦我们有了我们的表，它只会让他们安排给我们所需的索引映射。 .reduce((si,k) => (lut[k].forEach(e => !si.includes(e[0]) && si.push(e[0])),si) , []) 行有点滑稽。它所做的是为每条路径将其索引插入数组“如果”它不在数组中。所以我们从最依赖的一个 (6) 开始，然后推送 3、0 和 2。因此当轮到 5 时，我们不会再次推送相同的索引。