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, Dec 09 '21 at 13:16
Relevant: see [this answer](https://stackoverflow.com/a/58626840) by [georg](https://stackoverflow.com/users/989121/georg) — VLAZ, Dec 09 '21 at 13:18
@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, Dec 09 '21 at 13:45
@Nermin Ok I'll reopen and repost the answer for more visibility — Bergi, Dec 09 '21 at 14:06

Bergi · Answer 1 · 2021-12-09T14:11:33.957

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

score 0 · Accepted Answer · answered Dec 09 '21 at 14:19

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))` — VLAZ, Dec 09 '21 at 14:53

score 0 · Answer 3 · answered Dec 09 '21 at 18:19

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

Intersection between multiple Sets

EDIT/Solution

3 Answers3