6

我正在寻找工会。我想根据其中一个索引是否与另一对索引共享一个数字来对数字对进行分组。所以：

我有一系列对，例如：

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)
}
4

3 回答 3

3

啊。您正在寻找的算法是 dfs 森林。维基百科有一些关于树木和森林的好东西。

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 平方算法。它应该和现在人类发现的一样快。

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

事实上，这是一个由@Dij回答的 JSFiddle。您会看到是否将边数增加一倍，执行时间增加四倍（yikes）。他的算法确实有一个有趣的特点，没有最优/非最优情况；一切都需要相同的时间。然而，即使在最不理想的情况下，dfs 森林仍然比统一速率略快。

于 2017-07-26T02:17:30.340 回答
3

方法：

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]]));

于 2017-07-26T00:16:50.623 回答
1

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

为不包含先前过滤数组元素的元素过滤原始数组。

用于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);

于 2017-07-26T01:20:07.563 回答