Javascript Union Pairs Union Find

Viewed 2341

I working on union finding. I want to group pairs of numbers based on whether one of the indices shares a number with an index of another pair. So:

I have an array of pairs such as these:

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

whats the best way to group them in unions such as this:

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

([1,3] and [3,8] go together because they share 3. That group unites with [6,8] because they share 8. Whats the best way to do this in javascript?

Here are other examples:

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

Edit Here's the method I'm currently using:

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)
}
3 Answers
Related