是否有一个javascript函数用于查找第一个集合，该集合包含一组集合中的每个元素(如果该组存在这样的集合)

Question

我正试图找到以下问题的解决方案，其中我有三个集合(从技术上讲是数组，但它们总是保证不会有重复元素，并且它们的元素总是按递增顺序排列(，并且我需要确定第一组数字，该第一组数字将包含每个集合中的恰好一个元素，并且本身没有重叠值(如果给定该组数字可以存在这样的一组数字(：

const a = [1, 2, 3];
const b = [1, 2];
const c = [1, 2];
// In this case, the first eligible set would be [3, 1, 2].
// Order matters, so a return of [3, 1, 2] would indicate that a: 3, b: 1, and c: 2.
findFirstCoalescingSetAmongGroupOfSets([a, b, c]);
const d = [1, 2];
// In this case, there would be no eligible set.
findFirstCoalescingSetAmongGroupOfSets([a, b, c, d]);

在我进入一个我怀疑必须递归并对ol’面条征税的解决方案之前，我想看看javascript是否有一个内置的函数来确定这类事情，或者我是否缺少一个简单的方法。我在MDN上对Set的调查中运气不佳。

该解决方案需要适用于任意数量的集合；聚结集"；。

Answer 1

这个问题显然等价于在二分图中找到最大基数匹配。对于每个集合，在图形的一个部分中创建一个顶点，对于每个项，在图的另一个部分创建一个节点，并在集合及其元素之间添加边。之后，您需要找到一个最大基数匹配，并检查它是否包含第一部分的所有顶点。

在二分图中寻找最大基数匹配的算法是众所周知的，例如，参见上面链接的维基百科文章中的短列表；当然，你可以在这个话题上找到很多其他的资源。你甚至可能试图找到一些实现其中一种算法的Javascript库，尽管很明显，JS的标准库中不包含这种算法

这会发现一些聚结集，但不是第一个(顺便说一句，你如何定义"第一个"？(；然而，我认为对标准算法进行简单的修改可以让你找到字典式的第一匹配。

还要注意，不仅你的问题可以简化为在二分图中找到最大基数匹配，而且反过来也是正确的。也就是说，给定一些二分图，只需从图的一部分创建等于顶点邻接列表的集合，就可以减少找到与问题匹配的最大基数的问题。因此，这两个问题是等价的(我甚至可以说，它们完全是同一个问题，因为你所说的"集合"只是二分图的邻接表(，因此你很可能找不到任何比匹配问题更简单的算法。特别是，没有贪婪算法会起作用。(或者，也许你会找到一个更好的算法，但这将是一个真正伟大的科学成就。(

Answer 2

根据@Petr的建议，我从这里选择了一种可能的(Kuhn(算法。

const findFirstCoalescingSetAmongGroupOfSets = array => {
const indices = array.reduce((m, a, i) => {
a.forEach(v => m.set(v, [...(m.get(v) || []), i]));
return m;
}, new Map); // map values to indecies in original array of arrays
const p2 = Array.from(indices.keys()).reduce((m, v, i) => m.set(v, i), new Map); // map values to indecies in indices 
const p2i = new Map(Array.from(p2).map(([k,v]) => [v, k])); // map indecies to values in indices
const n = array.length, k = p2.size; // n - vertices in original array indecies partile, k - vertices in all possible values partile
const g = array.map(e => e.map(v => p2.get(v))); // adjacency lists of a bipartite graph
const mt = new Array(k).fill(-1); // mt[i] - index of vertice from first partile connected with ith vertice from second partile, or -1
let used; // temporary array to fix attended vertices during recursion
// in recursion we got around unattended vertices of first graph partile trying to enlarge chain of vertices pairs (to, mt[to]) for each new vertice from first graph partile
const try_kuhn = v => {
if (used[v]) return false;
used[v] = true;
for (let i = 0; i < g[v].length; ++i) {
const to = g[v][i];
if (mt[to] === -1 || try_kuhn(mt[to])) {
mt[to] = v;
return true;
}
}
return false;
}
for (let v = 0; v < n; ++v) {
used = new Array(n).fill(false);
try_kuhn(v);
}
const result = new Array(n);
for (let i = 0; i < k; ++i) {
if (mt[i] != -1) {
result[mt[i]] = p2i.get(i);
}
}
//console.log("array =", array);
//console.log("indices=", indices);
//console.log("p2=", p2);
//console.log("p2i=", p2i);
//console.log("g=", g);
for (let i = 0; i < n; ++i) {
if (result[i] === undefined) return;
}
return result;
}
console.log(findFirstCoalescingSetAmongGroupOfSets([[4], [1, 2, 3, 4], [2, 3], [1]]));
console.log(findFirstCoalescingSetAmongGroupOfSets([[1, 3, 4], [2, 3, 4], [1, 2], [1, 2, 3, 4]]));
console.log(findFirstCoalescingSetAmongGroupOfSets([[1, 3], [2, 3], [1, 2]]));
console.log(findFirstCoalescingSetAmongGroupOfSets([[1, 2, 3, 4, 5], [1], [1]]));
console.log(findFirstCoalescingSetAmongGroupOfSets([[1, 2, 3], [1, 2], [1, 2]]));