Javascript: Set Data Structure: intersect

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)

As of June 2024, Set has been added to the spec: you can 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/[email protected]/minified.js"></script>

It is live in Safari 17 and Chrome 122 and SerenityOS, and also supported in Node 22.

For other engines and backwards compatibility, you could use Immutable.js's Set, which inspired that proposal:

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

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

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

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

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

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.

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] 

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 ]

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

Micro-optimizers might find it worth noting that, given small-enough input sets, intersections can be computed without loops.

 const BANANA = 1 const LEMON = 2 const APPLE = 4 const CARROT = 8 const CORN = 16 const fruits = BANANA | LEMON | APPLE const yellowFoods = BANANA | LEMON | CORN const intersection = fruits & yellowFoods console.log('BANANA in set:', Boolean(BANANA & intersection)) console.log('LEMON in set:', Boolean(LEMON & intersection)) console.log('APPLE in set:', Boolean(APPLE & intersection)) console.log('CARROT in set:', Boolean(CARROT & intersection)) console.log('CORN in set:', Boolean(CORN & intersection)) 

This works because, when using powers of two, bitwise OR and XOR become equivalent to set union and intersection operations, respectively.