create arrays of intersecting values

Question

Here are some arrays of values:

values = [
  [1,2,3],
  [2,3,4],
  [8,9,10],
  [9,10,11],
  [13,14,15]
];

I want to create new numerically sorted arrays of the union of arrays' values when there is an intersection of the values of two or more arrays.

Values in these new sorted arrays will be unique.

If an array does not intersect any other arrays, then we include that array in the results (e.g. [13,14,15] in the example).

For example:

clusters = [
  [1,2,3,4],
  [8,9,10,11],
  [13,14,15]
];

Since value[0] and value[1] intersect, we add a union of their values to clusters.

Since value [2] and value[3] intersect, we add a union of their values to clusters.

Since value[4] does not intersect value[0] through value[4], we just add value[5] to clusters.

---

Now, if there was a value[6] = [3, 100], then our clusters would look like this:

clusters = [
  [1,2,3,4,100],
  [8,9,10,11],
  [13,14,15]
];

because value[6] intersected value[0] and value[1], so we add to their union.

Is there a technique or optimal way to do this?

In my example, the original arrays are sorted, but that might not necessarily be the case.

Answer 1

Use for-loop and for each sub array check with previous array (last) whether it has intersection. If intersection, add the merged array to result.

values = [
  [1, 2, 3],
  [2, 3, 4],
  [8, 9, 10],
  [9, 10, 11],
  [13, 14, 15],
];

const intersect = (arr1, arr2) => {
  const both = [...arr1, ...arr2];
  const uniq = [...new Set(both)];
  return uniq.length !== both.length ? uniq : null;
};

const compact =  (arrArr) => {
  if (arrArr?.length < 2) {
    return arrArr;
  }
  const res = [];
  let last = arrArr[0];
  for (let i = 1; i < arrArr.length; i++) {
    last = intersect(last, arrArr[i]) ?? (res.push(last), arrArr[i]);
  }
  res.push(last);
  return res;
};

console.log(compact(values))

Answer 2

Here is an edited snippet in response to the comments using .reduceRight(), seeding the accumulator with a copy of the passed array, and still using some() and includes() to find duplicates.

reduceRight() iterates the array in reverse, while findIndex() searches from the beginning. When a match is found the current iterated array is pushed to the matched array and then the current element is removed from the accumulator using splice().

function clusterDuplicates(arr) {
  return arr
    .reduceRight((a, arr, i) => {
      if (i) {
        let j = a.slice(0, i).findIndex(_arr => arr.some(x => _arr.includes(x)));

        if (~j) {
          a[j].push(...arr);
          a.splice(i, 1);
        }

      }
      return a
    }, [...arr])
    .map(arr => [...new Set(arr)].sort((a, b) => a - b));
}

console.log(clusterDuplicates([[1, 2, 3], [3, 4, 2], [8, 9, 10], [9, 11, 10], [14, 13, 15]]));
console.log(clusterDuplicates([[1, 2], [3, 4], [2, 3]]));

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

Original Answer

As noted in the comments, this fails to look ahead for duplicates.

Here's a fairly concise implementation using reduce() looking for intersections using some() and includes(). The result is then mapped to remove duplicates using Sets and then sorted.

const
  values = [[1, 2, 3], [3, 4, 2], [8, 9, 10], [9, 11, 10], [14, 13, 15]],
  result =
    values
      .reduce((a, arr) => {
        let i = a.findIndex(_arr => arr.some(x => _arr.includes(x)));

        if (i === -1) {
          i = a.push([]) - 1;
        }

        a[i].push(...arr);

        return a
      }, [])
      .map(arr => [...new Set(arr)].sort((a, b) => a - b));

console.log(result);

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

Answer 3

To see if 2 arrays intersect, a nice an simple way is to compare the set of both arrays together's size, with each array's set size, and if there different we know they intersect.

Below is an example..

const values = [
  [1,2,3],
  [8,9,10],
  [2,3,4],
  [9,10,11],
  [13,14,15]
];

function arrayItersect(a,b) {
  return new Set([...a,...b]).size !==
    new Set(a).size + new Set(b).size;
}

function joinIntersections(v) {
  const a = [...v]; //make a copy
  for (let l = 0; l < a.length-1; l += 1) {
    let l2 = l + 1;
    while (l2 < a.length) {
      if (arrayItersect(a[l], a[l2])) {
        a[l] = 
          [...new Set(
          [...a[l],...a.splice(l2, 1)[0]]
          )];
      } else l2 ++;
    }
  }
  return a;
}

console.log(joinIntersections(values));