Javascript: Set Data Structure: intersect

Question

Trying to get two data sets to intersect but I can't do it. For example, in my code below, intersecting mySet and mySet2 should yield "1" since they both have a value of "1" in their set.

var mySet = new Set();
var mySet2=new Set();
mySet.add(1);
mySet.add(2);
mySet.add("HELLOOOOO");
mySet2.add("hi");
mySet2.add(1);


var a = Array(mySet, mySet2);
console.log(a);

mySet.forEach(function(value) {
    console.log(value);
});


mySet2.forEach(function(value) {
    console.log(value);
});

function intersection_destructive(a, b)
{
    var result = new Array();
    while( mySet.length > 0 && mySet2.length > 0 )
    {
        if      (mySet[0] < mySet2[0] ){ mySet.shift(); }
        else if (mySet[0] > mySet2[0] ){ mySet2.shift(); }
        else /* they're equal */
        {
            result.push(mySet.shift());
            mySet2.shift();
        }
    }

    return result;
}

Set 1 and Set 2 both have "1" in it but my function (intersection_destructive) doesn't return it. I'm not sure how to intersect them, I searched stackoverflow and found intersection_destructive but it didn't work for me, I also tried:

array1.filter(function(n) {
    return array2.indexOf(n) != -1
});

as per this: Simplest code for array intersection in javascript

but I get an error on filter when I try to run it.

Answer 1

Sadly as you've figured out there are no native intersection or union operations. It's not terribly complex to find the intersection though:

let a = new Set([1,2,3])
let b = new Set([1,2,4])
let intersect = new Set([...a].filter(i => b.has(i)));
console.log(...intersect)

Answer 2

To get the intersection, you can iterate the items of a set and check if they belong to the other one:

var intersect = new Set();
for(var x of mySet1) if(mySet2.has(x)) intersect.add(x);

In ES7 you can simplify it with array comprehensions or generator comprehensions:

var intersect = new Set((for (x of mySet1) if (mySet2.has(x)) x));

Answer 3

With the currently Stage 3 proposal https://github.com/tc39/proposal-set-methods, you could use:

mySet.intersection(mySet2);

const set1 = new Set([1, 2, 3]);
const set2 = new Set([1, 2, 4]);

const intersect = set1.intersection(set2);
console.log(...intersect);

<script src="https://unpkg.com/core-js-bundle@3.27.1/minified.js"></script>

Until then, you could use Immutable.js's Set, which inspired that proposal:

Immutable.Set(mySet).intersect(mySet2);

Answer 4

You have been trying array intersections methods. You cannot use them on ES6 sets. Instead, use

function intersect(...sets) {
    if (!sets.length) return new Set();
    const i = sets.reduce((m, s, i) => s.size < sets[m].size ? i : m, 0);
    const [smallest] = sets.splice(i, 1);
    const res = new Set();
    for (let val of smallest)
        if (sets.every(s => s.has(val)))
             res.add(val);
    return res;
}

Answer 5

One technique for intersecting sets is to take the smallest set and check for each of its values in the other sets, removing the value if any set does not contain it. Although runtime is O(n x m), where n is the set length and m is the number of sets, the n is likely to be much smaller if the sets are not all the same length.

function setsIntersection(...sets) {
  if (sets.length < 1) {
    return new Set();
  }

  let min_size = sets[0].size;
  let min_set_index = 0;

  for (let i = 1; i < sets.length; i++) {
    const size = sets[i].size;
    if (size < min_size) {
      min_size = size;
      min_set_index = i;
    }
  }

  const temp_swap_set = sets[0];

  sets[0] = sets[min_set_index];
  sets[min_set_index] = temp_swap_set;

  const result = new Set(sets[min_set_index]);
  for (let i = 1; i < sets.length; i++) {
    for (const v of result) {
      if (!sets[i].has(v)) {
        result.delete(v);
      }
    }
  }
  return result;
}

Answer 6

You could iterate the set and create a new set for the common values.

const
    intersectSets = (a, b) => {
        const c = new Set;
        a.forEach(v => b.has(v) && c.add(v));
        return c;
    },
    a = new Set([1, 2, 3]),
    b = new Set([1, 2, 4]),
    c = new Set([1, 2, 4, 5]),
    n = new Set([1, 2]);

console.log(...[a, b, c, n].reduce(intersectSets));

Answer 7

This will work on both Sets and Arrays. It will return whatever the type of set1 is. Arguments can be mixed types.

/**
 * Returns the intersection of ES6 Set objects. i.e., returns a new set with only elements contained in all the given sets.
 * 
 * @param {Set|Array} set1 First set
 * @param {Array<Array|Set>} sets Other sets
 * @returns {Set|Array} Intersection
 */
export function intersection(set1, ...sets) {
    if(!sets.length) {
        return set1;
    }
    const tmp = [...set1].filter(x => sets.every(y => Array.isArray(y) ? y.includes(x) : y.has(x)));
    return Array.isArray(set1) ? tmp : new Set(tmp);
}

I built it for working with Sets, but then I realized it's probably more expensive to convert an array into a set just so I can use .has on it once than to just use .includes.

Answer 8

From the example: intersection_destructive takes 2 ARRAYS not 2 SETS. Here is your code working with the intersection_destructive example.

// These must be sorted arrays!
var mySet = [1,2,6];
var mySet2 = [1,2,5];

// Takes 2 Arrays
// array properties: shift
function intersection_destructive(a, b)
{
    var result = [];
    while( a.length > 0 && b.length > 0 )
    {
        if      (a[0] < b[0] ){ b.shift(); }
        else if (a[0] > b[0] ){ b.shift(); }
        else /* they're equal */
        {
            result.push(a.shift());
            b.shift();
        }
    }

    return result;
};

var result = intersection_destructive(mySet, mySet2);
console.log(result); // Output: [1,2]

Answer 9

To use the Array.filter() is a useful pattern. You need to convert your sets to array's using Array.from(). Also make sure that you filter through smaller set into the bigger one. see fiddle

var mySet = new Set();
var mySet2=new Set();
mySet.add(1);
mySet.add(2);
mySet.add("HELLOOOOO");
mySet2.add("hi");
mySet2.add(1);

console.log(intersection_destructive(mySet, mySet2));

function intersection_destructive(a, b)
{

    // filter over the shorter set and convert sets to Array's so we have filter
    if (a.length > b.length) {
        var array1 = Array.from(a);
        var array2 = Array.from(b);
    } else {
        var array1 = Array.from(b);
        var array2 = Array.from(a);
    }

    var result = array1.filter(function(n) {
        return array2.indexOf(n) != -1
    });

    return result;
}

Answer 10

Intersection of two arrays

function intersection(arr1, arr2) {
  const set2 = new Set(arr2)
  const com = arr1.filter(a => set2.has(a))
  return [...new Set(com)]
}


console.log(intersection([1, 2, 3], [1, 2, 4])) // [ 1, 2 ]
console.log(intersection([1, 2, 4], [2, 2, 4, 4])) // [ 2, 4 ]