Intersection between multiple Sets

Question

I've seen previously how to take the intersect between two sets: Javascript: Set Data Structure: intersect

For example,

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

But how do I extend this to a general solution with multiple (very many) sets? E.g. like this:

let a = new Set([1,2,3]) let b = new Set([1,2,4]) let c = new Set([1,2,4,5]) ... let n = new Set([1,2]) let intersect = ...

I would like to define a function that returns the intersection of an unknown amount of sets, if possible

function intersection(a, ...args) { return ... }

EDIT/Solution

Thanks to the comments I managed to come up with a solution:

function intersect(setA, setB, ...args) { const intersection = new Set([...setA].filter((i) => setB.has(i))) if (args.length === 0) return intersection return intersect(intersection, args.shift(), ...args) }

One approach would be to create a recursive function, that takes two or more arguments. Intersect the first two arguments, and call the function again with the result and the remaining arguments. Continue until you have no more arguments left. — Andreas Louv
– Andreas Louv, Commented Dec 9, 2021 at 13:16
@Bergi the question in that thread is specificly for two sets, and that answer is pretty buried, and there's no incentive in that thread for coming up with better solutions for multiple sets. — Nermin
– Nermin, Commented Dec 9, 2021 at 13:45
@Nermin Ok I'll reopen and repost the answer for more visibility — Bergi
– Bergi, Commented Dec 9, 2021 at 14:06

Bergi · Accepted Answer · 2021-12-09 14:11:33Z

My solution from here deals with multiple sets:

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

A bit more elaborate:

function intersect(...sets) { const res = new Set(); if (sets.length) { sets.sort((a, b) => a.size-b.size); const smallest = sets.shift(); for (const val of smallest) { if (sets.every(s => s.has(val))) { res.add(val); } } } return res; }

Nermin · Accepted Answer · 2021-12-09 14:19:24Z

I actually extended this general recursive approach to more set operations as well

// A ∩ B ∩ ... const intersect = (setA, setB, ...args) => { const result = new Set([...setA].filter((i) => setB.has(i))) if (args.length === 0) return result return intersect(result, args.shift(), ...args) } // A ⋃ B ⋃ ... const union = (setA, setB, ...args) => { const result = new Set([...setA, ...setB]) if (args.length === 0) return result return union(result, args.shift(), ...args) } // A \ B \ ... const complement = (setA, setB, ...args) => { const result = new Set([...setA].filter((x) => !setB.has(x))) if (args.length === 0) return result return complement(result, args.shift(), ...args) }

union can be simplified a lot with a generator helper: function* concat(...xs) { for (const x of xs) yield* x; } which would allow you to do new Set(concat(...allSets))

Nina Scholz · Accepted Answer · 2021-12-09 18:19:02Z

My solution from here.

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

Collectives™ on Stack Overflow

Intersection between multiple Sets

EDIT/Solution

3 Answers 3

Comments

1 Comment

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

EDIT/Solution

3 Answers 3

Comments

1 Comment

Comments

Linked

Related