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森林仍然比統一費率略快。