N个集合的交集

Question

Mozilla有一个示例展示了如何交叉两个集合，像这样：

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

但是，最简洁（紧凑）的交集 N 个集合的方法是什么呢？谢谢。

- apostl3pol

---

“最佳”究竟指什么？最高效？最简单？最简洁？ - Bergi

@Bergi 实际上，我希望根据大家的意见得到几个不同的选择。但你说得对，我表达得不清楚。我会更新问题的描述。 - apostl3pol

Answer 1

你可以采用这种方法来减少一个包含多个集合的数组。

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

在使用原型和thisArg来进行过滤时，情况相同。

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

- Nina Scholz

Answer 2

在我以前的一篇回答中发现，我推荐以下方法：

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

它既优雅又高效 :-) 它的时间复杂度是线性的，与最小输入集的大小和集合数量成正比，而且在过程中不会构建任何不必要的临时数组。

- Bergi

Answer 3

这里是另一种方法，获取一组集合中的第一个集合，然后通过那些属于所有其他集合的元素来过滤它:

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

- Shidersz