JavaScript联盟对联盟查找

Question

我致力于联盟调查。我想根据一个索引与另一个索引是否共享一个数字来对数字对进行分组。所以：

我有对的阵列，如以下：

pairs: [[1,3], [6,8], [3,8], [2,7]] 

什么对他们在工会组的最佳方式如此：

[ [ 1, 3, 8, 6 ], [ 2, 7 ] ] 

（[1,3]和[3,8]因为他们共享而团队合作3.该团体与[6,8]合并，因为他们共享8.在javascript中执行此操作的最佳方式是什么？

以下是其他示例：

pairs: [[8,5], [10,8], [4,18], [20,12], [5,2], [17,2], [13,25],[29,12], [22,2], [17,11]] 

into [ [ 8, 5, 10, 2, 17, 22, 11 ],[ 4, 18 ],[ 20, 12, 29 ],[ 13, 25 ] ] 

编辑 这里是我目前使用的方法：

findUnions = function(pairs, unions){ 
    if (!unions){ 
     unions = [pairs[0]]; 
     pairs.shift(); 
    }else{ 
     if(pairs.length){ 
      unions.push(pairs[0]) 
      pairs.shift() 
     } 
    } 

    if (!pairs.length){ 
     return unions 
    } 
    unite = true 
    while (unite && pairs.length){ 
     unite = false 
     loop1: 
     for (i in unions){ 
      loop2: 
      var length = pairs.length; 
      for (j=0;j<length;j++){ 
       if (unions[i].includes(pairs[j][0])){ 
        if (!unions[i].includes(pairs[j][1])){ 
         unions[i].push(pairs[j][1]) 
         pairs.splice(j, 1) 
         j-=1; 
         length-=1 
         unite = true 
        }else{ 
         pairs.splice(j, 1) 
         j-=1 
         length-=1 
        } 
       }else if (unions[i].includes(pairs[j][1])){ 
        unions[i].push(pairs[j][0]) 
        pairs.splice(j, 1) 
        unite = true 
        j-=1 
        length-=1 
       } 
      } 
     } 
    } 
    return findUnions(pairs, unions) 
} 

Answer 1

方法：

finalArray = [], positions = {};  
for i to Array.length 
    for j=i+1 to Array.length 
     find match between arr[i] and arr[j] 
     if match found 
      pos = postion mapped to either i or j in positions 
      add elements of arr[i] or arr[j] or both depending on pos. 
return finalArray 

在该方法中，我们不断保存我们加入到finalArray在数组中的位置定位对象，随后我们可以使用这个对象来找到一个合适的位置来添加finalArray中匹配数组的元素。

function mergeArrays(finalArray, pos, subArray) { 
 
for (var k = 0; k < subArray.length; k++) { 
 
    if (finalArray[pos].indexOf(subArray[k]) < 0) 
 
     finalArray[pos].push(subArray[k]); 
 
} 
 

 
} 
 

 
function unionArrays(arr) { 
 
var finalArray = [arr[0]], 
 
    positions = { 
 
     0: 0 
 
    }; 
 
for (var i = 0; i < arr.length; i++) { 
 
    for (var j = i + 1; j < arr.length; j++) { 
 
     for (var k = 0; k < arr[i].length; k++) { 
 
      if (arr[j].indexOf(arr[i][k]) >= 0) { 
 
       if (i in positions) { 
 
        mergeArrays(finalArray, positions[i], arr[j]); 
 
        positions[j] = positions[i]; 
 
       } else if (j in positions) { 
 
        mergeArrays(finalArray, positions[j], arr[i]); 
 
        positions[i] = positions[j]; 
 
       } else { 
 
        var pos = finalArray.length; 
 
        finalArray.push([]); 
 
        mergeArrays(finalArray, pos, arr[i]); 
 
        mergeArrays(finalArray, pos, arr[j]); 
 
        positions[i] = positions[j] = pos; 
 
       } 
 
       break; 
 
      } 
 

 
     } 
 
    } 
 
    if (!(i in positions)) { 
 
     finalArray.push(arr[i]); 
 
     positions[i] = finalArray.length - 1; 
 
    } 
 
} 
 
return finalArray; 
 
} 
 
console.log(unionArrays([[1,3], [6,8], [3,8], [2,7]])); 
 
console.log(unionArrays([[8,5], [10,8], [4,18], [20,12], [5,2], [17,2], [13,25],[29,12], [22,2], [17,11]]));

Answer 2

为了满足可以迭代阵列的第一要求，内迭代过程从含有所有相邻索引一个新的数组排除当前阵列。检查相邻数组是否包含当前数组的一个或多个元素，如果是true，则将这些元素推送到新数组中。

为不包含先前过滤数组元素的元素过滤原始数组。使用Set删除数组中的重复条目。

const arr = [[1,3], [6,8], [3,8], [2,7]]; 
 

 
let res = []; 
 

 
for (const[key, [a, b]] of Object.entries(arr)) { 
 
    const adjacent = arr.filter((el, index) => index !== +key); 
 

 
const has = adjacent.filter(el => el.includes(a) || el.includes(b)); 
 
    res = [...res, ...has.filter(prop => !res.includes(prop))]; 
 
} 
 

 
let not = new Set(...arr.filter(([a, b]) => !res.some(([c, d]) => 
 
      a === c || b === d || a === d || b === c))); 
 

 
let set = new Set(); 
 

 
for (const [a, b] of res) { 
 
    if (!set.has(a)) set.add(a); 
 
    if (!set.has(b)) set.add(b); 
 
} 
 

 
res = [[...set], [...not]]; 
 

 
console.log(res);

Answer 3

啊。你正在寻找的算法是一个dfs森林。 Wikipedia在树木和森林上有一些好东西。

dfs森林只是一个dfs（深度优先搜索），直到没有未访问节点才运行。结果是连接和孤立子图（“树”）的图（“森林”）。这些是你所指的“工会”。

当每个节点映射到它所连接的节点时，深度优先搜索更容易（也更快）。因此，而不是这样的数据：

[[1,3], [6,8], [3,8], [2,7]] 

你想：

{1: [3], 2: [7], 3: [1, 8], 6: [8], 7: [2], 8: [6, 3]} 

转化你的数据是相当琐碎（和快速）：

function mapNodes(edges) { 
    let nodeMap = {} 

    edges.forEach(edge => { 
     let node1 = edge[0] 
     let node2 = edge[1] 

     if (!nodeMap[node1]) nodeMap[node1] = [node2] 
     else nodeMap[node1].push(node2) 

     if (!nodeMap[node2]) nodeMap[node2] = [node1] 
     else nodeMap[node2].push(node1) 
    }) 
    return nodeMap 
} 

那么DFS本身是一个简单的递归算法而dfs森林只是继续运行它，直到没有更多的未访问节点。这里有一个[编辑：不是这样了粗例如：

function dfsForest(nodeMap) { 
    let forest = [] 
    let nodes = Object.keys(nodeMap) 

    while (true) { 
     let root = +nodes.find(node => !nodeMap[node].visited) 
     if (isNaN(root)) break // all nodes visited 

     forest.push(dfs(root, nodeMap)) 
    } 
    return forest 
} 

function dfs(root, nodeMap, tree = []) { 
    if (tree.includes(root)) return tree // base case 

    tree.push(root) 
    nodeMap[root].visited = true 

    let connectedNodes = nodeMap[root] 
    for (let i = 0; i < connectedNodes.length; i++) { 
     let connectedNode = connectedNodes[i] 
     dfs(connectedNode, nodeMap, tree) 
    } 
    return tree 
} 

而这里的所有的一个JSFiddle。

编辑：

那么，我说这是粗糙的。我编辑了代码和小提琴，删除了额外的visitedNodes数组以及它创建的n-squared算法。它的速度应该和现在人类发现的一样快。

在我的测试中，重新格式化数据需要大约350毫秒，并且在5000个非最佳对上运行dfs森林。在最佳情况下，大约需要50毫秒。它降解得很好。例如，总边数加倍会使执行时间从1.5到2.5倍增加，这取决于配对的最优化。

实际上，这里的JSFiddle由@Dij回答。你会看到，如果你的边数增加一倍，执行时间增加四倍（yikes）。他的算法确实有一个有趣的功能，因为没有最佳/非最佳的情况;一切都需要相同的时间。然而，即使在最不理想的情况下，dfs森林仍然比统一费率略快。