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

Question

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

3

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

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]

由于元素数量较多，我不想使用递归。有没有一种方式可以通过一个数组中包含在每个其他数组中的元素来对此数组列表进行排序，以便我可以通过迭代处理它们？

编辑：我认为可以通过以下方式解决这个问题：为组成的每条路径分配一个权重：包含在每个路径中的节点之和乘以该节点在其他路径中出现的次数，然后按长度升序和权重降序排序 - 但这只是我的猜测...

- deblocker

@Vld：我昨天刚读了你提到的那篇文章，我必须承认我还在努力消化中...重点是：它们也可以具有相等的长度，按长度排序是我的第一次尝试，但在一些更复杂的图形中不幸地失败了。 - deblocker

@deblocker 是的，我也花了一些时间来处理那篇文章，但我发现其中的技术很有趣。有点烦人的是，你必须修改你的算法才能利用它们，但这比堆栈溢出要好。无论如何，一个简单的按长度排序不会太难 arr.sort((a, b) => a.length - b.length)) 可以通过长度对包含数组的数组进行排序示例。这只是单层，但深入多层将是遍历所有内容并基本上排序任何遇到的数组的问题。 - VLAZ

@Vld：顺便说一下，如果你感兴趣的话，还有一个很棒的礼物：JavaScript中的定点组合器：记忆化递归函数。 - deblocker

@deblocker 很好，谢谢！我稍后会看一下 :) - VLAZ

这还是水平矩形分布问题吗？它变得比我想象的更加复杂。希望你能找到解决方案。 - m69 ''snarky and unwelcoming''

显示剩余4条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Redu · Accepted Answer

我猜...如果我理解正确的话，您是想进行依赖关系排序。那么我认为实现此任务的一种可能方法如下。这是我能想到的一种方式，但可能还有更简单的解决方案。

我们必须将彼此依赖的连续项分组（例如[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个依赖项。因此，我们按照依赖项数量进行排序（.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时，我们不会再次推送相同的索引。