Intersection of N sets

Question

Mozilla has an example showing how to intersect two sets like so:

var intersection = new Set([...set1].filter(x => set2.has(x)));

but what's the most concise (compact) way to intersect N sets? Thanks.

By "best", what are you looking for exactly? Most efficient? Simplest? Most concise? — Bergi, Mar 07 '19 at 21:26
@Bergi Actually I was hoping to get a few different options depending on people's opinions. But you're right, I'm not being clear. I'll update the question. — apostl3pol, Mar 07 '19 at 21:31

score 6 · Accepted Answer · answered Mar 07 '19 at 21:32

You could take this approach and reduce an array of sets.

var set1 = new Set([1, 3, 4, 5, 6, 8]),
    set2 = new Set([1, 4, 5, 7, 9]),
    set3 = new Set([1, 4, 5, 8, 9]),
    intersection = [set1, set2, set3].reduce((a, b) => new Set([...a].filter(x => b.has(x))));

console.log([...intersection]);

Same with using a prototype and thisArg for filtering.

var set1 = new Set([1, 3, 4, 5, 6, 8]),
    set2 = new Set([1, 4, 5, 7, 9]),
    set3 = new Set([1, 4, 5, 8, 9]),
    intersection = [set1, set2, set3].reduce((a, b) => 
        new Set([...a].filter(Set.prototype.has, b)));

console.log([...intersection]);

score 3 · Answer 2 · answered Mar 07 '19 at 21:38

Found in an old answer of mine, I recommend this:

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

It's both elegant and efficient :-) Its time complexity is linear to the size of the smallest input set and linear to the number of sets, and it doesn't construct any unnecessary temporary arrays on the way.

score 0 · Answer 3 · answered Mar 07 '19 at 22:10

Here is another way, getting the first set of one array of sets, and then filter this one by those elements that belongs to all the other sets:

let sets = [
    new Set([1, 3, 4, 5, 6, 8]),
    new Set([1, 4, 5, 7, 9]),
    new Set([1, 4, 5, 8, 9])
];

// Generate the intersection.
let intersection = new Set([...sets[0]].filter(
    x => sets.slice(1).every(s => s.has(x))
));

console.log([...intersection]);

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

Intersection of N sets

3 Answers3