Remove sub-array contains common elements

Question

As the title, if the input is [[1,2], [3,4], [1,3], [5,6], [6,5]], output should be [[1,2,3,4], [5,6]]. It's wrong on the recursive part. In my code, after running it, I will get [[1,2,3],[1,3,4],[5,6]], which means I need once more merge, but I'm confused how to continue the code until no sub-array contains common element.

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;
}

sorry, it's a typo, the output should be [[1,2,3,4], [5,6]]. — Yuqi Shi, May 16 '17 at 15:00
Possible duplicate of [How to merge two arrays in Javascript and de-duplicate items](http://stackoverflow.com/questions/1584370/how-to-merge-two-arrays-in-javascript-and-de-duplicate-items) — gforce301, May 16 '17 at 15:13
I don't understand the problem. You need to describe it more clearly, and/or provide more examples. — , May 16 '17 at 19:46

Nina Scholz · Answer 1 · 2017-05-18T06:03:51.737

You could use two hash tables, one for the items and their groups and on for the result sets.

Basically the algorithm generates for the same group an object with a property and an array, because it allowes to keep the object reference while assigning a new array.

The main part is iterating the outer array and then the inner arrays and check inside, if it is the first item, then check the hash table for existence and if not exists, generate a new object with a values property and an empty array as value. Also assign the actual object to sets with item as key.

In a next step, the hash table is checked again and if not exist, then assign the object of the first element.

To maintain only unique values, a check is made and if the item does not exist, the item is pushed to the hash table's values array.

Then a part to join arrays follows by checking if the object of the first item is not equal to object of the actual item. If so, it delete from sets the key from the actual items's values first item and concat the array of the actual items to the first item's object's values. Then the values object is assigned to the actual item's object.

Later the sets are maped to the result set with iterating the sets object and the values property is taken as value.

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; }

score 0 · Answer 2 · edited May 18 '17 at 00:32

I figured it out. Here is the code:

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;
}

Remove sub-array contains common elements

2 Answers2

Linked