Delete sub-array contains common elements

Question

As a name, if the input is [[1,2], [3,4], [1,3], [5,6], [6,5]], the output should be [[1, 2,3,4 ], [5,6]]. This is incorrect in the recursive part. In my code, after starting, I will get [[1,2,3], [1,3,4], [5,6]], which means I need to merge again, but I'm confused how to continue the code until a common element is found.

Here is my code

function need_merge_or_not(arr)
{
  for (var i = 0; i <= arr.length-1; i++) {
      for (var j = i+1; j <= arr.length-1; j++) {
        var arr_new = arr[i].concat(arr[j]);
        //remove deplicates
        var arr_merge = arr_new.filter(function (item, pos) {return arr_new.indexOf(item) == pos});
        if (arr_merge.length < arr_new.length) {
          return true;
        }
      }
  }
  return false;
}


function merge(arr)
{
  if (arr.length >= 2) {
    for (var i = 0; i <= arr.length-1; i++) {
      for (var j = i+1; j <= arr.length-1; j++) {
        var arr_new = arr[i].concat(arr[j]);
        var arr_merge = arr_new.filter(function (item, pos) {return arr_new.indexOf(item) == pos});
        if (arr_merge.length < arr_new.length) {
          arr.splice(arr.indexOf(arr[i]), 1);
          arr.splice(arr.indexOf(arr[j]),1);
          arr.push(arr_merge);
        }
      }
        if (need_merge_or_not(arr)) {
          return merge(arr);
        }
    }
  }
  return arr;
}

Answer 1

You can use two hash tables, one for the elements and them groups, and for the result sets.

Basically, the algorithm generates an object with a property and an array for the same group, since it allows you to save a reference to the object when assigning a new array.

- , , , - , values ​​ . sets .

- , , .

, , , -.

, . , sets . .

sets sets, values ​​ .

var array = [[1, 2], [3, 4], [1, 3], [5, 6], [6, 5]],
    groups = {},
    sets = {},
    result;
    
array.forEach(function (a) {
    a.forEach(function (b, i, bb) {
        if (i === 0 && !groups[b]) {
            groups[b] = { values: [] };
            sets[b] = groups[b];
        }
        if (!groups[b]) {
            groups[b] = groups[bb[0]];
        }
        if (groups[b].values.indexOf(b) === -1) {
            groups[b].values.push(b);
        }
        if (groups[bb[0]] !== groups[b]) {
            delete sets[groups[b].values[0]];
            groups[bb[0]].values = groups[bb[0]].values.concat(groups[b].values);
            groups[b].values = groups[bb[0]].values;                    
        }
    });    
});

result = Object.keys(sets).map(function (k) {
    return sets[k].values;
});

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Hide result

Answer 2

. :

function merge(arr){
  var input = [];
  for(var i = 0; i < arr.length; i++){
    input.push(arr[i]);
  } 
  if (arr.length >= 2) {
    for (var i = 0; i < arr.length; i++) {
      for (var j = i+1; j < arr.length; j++) {
        var arr_new = arr[i].concat(arr[j]);
        //remove duplicates
        var arr_merge = arr_new.filter(function (item, pos) {return arr_new.indexOf(item) == pos});
        if (arr_merge.length < arr_new.length) {
          arr.splice(arr.indexOf(arr[i]), 1, arr_merge);
          arr.splice(arr.indexOf(arr[j]),1);
          j--;
        }
      }   
    }
    if (!arraysEqual(input, arr)) {merge(arr)};
  }
  return arr;
  //Input:[[1,2], [3,4], [1,3], [5,6], [6,5]]
  //Output:[[1,2,3,4], [5,6]]
}

function arraysEqual(a, b) {
  if (a === b) return true;
  if (a == null || b == null) return false;
  if (a.length != b.length) return false;

  for (var i = 0; i < a.length; ++i) {
    if (a[i] !== b[i]) return false;
  }
  return true;
}