线组合算法

Question

array  = [[1, 2], [13, 14], [4, 5], [80, 30], [12, 14], [10, 90], [3, 2], [6, 9], [1, 5], [4, 5], [5, 9], [4, 3], [13, 12]] 
//expected
output = [[1, 2], [13, 14], [4, 5], [80, 30],           [10, 90], [3, 2], [6, 9],         [4, 5], [5, 9], [4, 3], [13, 12]]

你可以把子数组看成线，例如，[1,2]是一条从点1连接到点2的线。因此，[1,2],[3,2],[4,3],[4,5],[4,3]将与连接点1的几条短线相关联到5点，因为1点到2点、2点到3点、3点到4点、4点到5点都有一条线连接。

如果数组包含较大的单行，即点 1 到点 5，则应将其过滤掉。这是为了删除所有较长的线，这些线已经在更短的线中定义了它们的点。可以使用什么算法来解决这个问题？

我已经在 https://codepen.io/Maximusssssu/pen/jOYXrNd?editors=0012

尝试了下面的代码

第一部分以升序输出所有子数组以提高可读性，而对于第二部分，我尝试了 include() 方法来检查子数组中是否存在节点，并获取其位置。

array  = [[1, 2], [13, 14], [4, 5], [80, 30], [12, 14], [10, 90], [3, 2], [6, 9], [1, 5], [4, 5], [5, 9], [4, 3], [13, 12]]

array_ascending_arr = [];

for (let i = 0; i < array.length; i++) {
  let subarrayy = array[i].sort(function(a, b) {
    return a - b
  });
  array_ascending_arr.push(subarrayy);
}

console.log(array_ascending_arr) // output all subarrays in ascending order back into array

for (let k = 1; k < 5; k++) {
  for (let m = 0; m < array.length; m++) {
    for (let i = 1; i < 2; i++) {
      if (array_ascending_arr[m].includes(k) == true) {
        console.log(m)
      }
    }

  }
  console.log(".......")
}

Answer 1

你可以试试邻接表。我对该算法的理解是，如果两对共享一条边，它们将组合形成一条新边，直到所有集合都是唯一的。

Answer 2

主要思想是计算中间元素数量的差异而不是价值
如果我们有 [[1,2],[14,10],[4,6],[9,2] 使得序列 = [1,2,4,6,9,10,14]（已排序）

return 增量值：

[1,2] -> d:1
[9,2] -> d:3 // the 9 is three positions away from the 2

因此原则是从最远的值开始处理到最远的值
（其他排序条件是次要的，主要用于调试）

注意：重复对也被剔除

const
  test1 = [[1,2],[13,14],[4,5],[80,30],[12,14],[10,90],[3,2],[6,9],[1,5],[4,5],[5,9],[4,3],[13,12]]
, test2 = [[1,2],[4,5],[30,80],[12,18],[10,90],[2,3],[6,9],[1,5],[4,6],[5,9],[3,4],[12,13],[12,14],[14,15],[15,18]]
  ;

console.log('test1:\n', JSON.stringify( combination( test1 )))
console.log('test2:\n', JSON.stringify( combination( test2 )))

function combination(arr)
  {
  let 
    nodes = arr.flat().sort((a,b)=>a-b).filter((c,i,{[i-1]:p})=>(c!==p))
  , sets  = nodes.map(g=>[g])
  , bads  = []
    ;
  arr                    // i:index, s:start(min), e:end(max),     d: delta
  .map(([v0,v1],i)     => ({i,s:Math.min(v0,v1),e:Math.max(v0,v1), d:Math.abs(nodes.indexOf(v0) - nodes.indexOf(v1))}))
  .sort((a,b)          => (a.d-b.d) || (a.s-b.s) || (a.e-b.e) || (a.i-b.i) )
  .forEach(({i,s,e,d}) =>
    {
    let 
      gS = sets.find(n=>n.includes(s))
    , gE = sets.find(n=>n.includes(e))
      ;
    if (gS === gE) { bads.push(i)                }
    else           { gS.push(...gE); gE.length=0 }
    })

  //console.log( sets.filter(a=>a.length).map(a=>JSON.stringify(a)).join(' - ') )
  return arr.filter((x,i)=>!bads.includes(i))
  }

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

Answer 3

因此，据我了解，您正在尝试删除范围大于范围小于范围的任何数字集。以下代码应执行此操作：

array.filter(pair => {
  // Get the smaller and larger numbers from the pair
  const [small, big] = pair.sort((a,b) => a-b)
  
  // Check if this pair is larger than any others
  return !array.some(test => {
    const [testSmall, testBig] = test.sort((a,b) => a-b)

    return big > testBig && small < testSmall
  })
})

请注意，这不会删除重复项。

如果您不介意子数组在最终数组中重新排序，您可以通过在开头对它们进行排序来稍微简化它：

array
  .map(pair => pair.sort((a,b) => a-b))
  .filter(([s, b], _, arr) => !arr.some(([ts, tb]) => b>tb && s<ts))

线组合算法

Line combination algorithm

javascript

arrays

algorithm