Javascript Union Pairs Union Найти

Метод:

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, в объекте position, а позже мы можем использовать этот объект, чтобы найти подходящую позицию для добавления элементов совпадающих массивов в 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]]));

Ах. Алгоритм, который вы ищете, - это лес 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 просто продолжает выполнять его до тех пор, пока не останется непосещенных узлов. Вот [EDIT: не так] грубый пример:

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-квадратов. Он должен быть примерно таким же молниеносно быстрым, как сейчас.

В моих тестах требуется около 350 миллисекунд, чтобы переформатировать данные И запустить лес dfs на 5000 очень неоптимальных пар. В оптимальном случае это занимает около 50 миллисекунд. И деградирует очень хорошо. Например, удвоение общего количества ребер увеличит время выполнения от 1,5 до 2,5 раз, в зависимости от того, насколько оптимальны пары.

Фактически, вот JSFiddle с ответом @Dij. Вы увидите, если вы удвоите количество ребер, время выполнения увеличится в четыре раза (yikes). У его алгоритма есть интересная особенность: нет оптимальных/неоптимальных случаев; все занимает одинаковое количество времени. Однако даже в самом неоптимальном случае лес dfs по-прежнему немного быстрее, чем эта фиксированная скорость.

Чтобы выполнить первое требование, вы можете выполнить итерацию массива, в рамках процедуры итерации исключить текущий массив из нового массива, содержащего все соседние индексы. Проверьте, содержат ли соседние массивы один или несколько элементов текущего массива, если 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);