2

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

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' noodle 征税之前，我想看看 javascript 是否有一个内置函数来确定这类事情，或者是否有一个简单的方法我'米失踪。我Set对MDN的调查没有运气。

该解决方案将需要适用于我正在寻找这个“合并集”的任意数量的集合。

4

2 回答 2

1

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

在二分图中找到最大基数匹配的算法是众所周知的，例如，参见上面链接的 Wikipedia 文章中的简短列表；当然，您可以找到有关此主题的许多其他资源。您甚至可以尝试找到一些实现其中一种算法的 Javascript 库，尽管显然 JS 的标准库不包含此类算法。

这会找到一些合并集，但不是第一个（顺便说一下，你如何定义“第一个”？）；但是，我认为对标准算法的简单更改将允许您找到字典上的第一个匹配项。

另请注意，不仅您的问题可以简化为在二分图中找到最大基数匹配，而且反之亦然。也就是说，给定一些二分图，只需创建等于图的一部分顶点的邻接列表的集合，因此您减少了找到与您的问题匹配的最大基数的问题。所以这两个问题是等价的（我什至会说它们是完全相同的问题，因为你所说的“集合”只是二分图的邻接列表），因此你很可能无法找到任何更简单的算法那些已经知道匹配问题的人。特别是，没有贪心算法会起作用。（或者，好吧，也许你会找到更好的算法，但这将是一项非常伟大的科学成就。）

于 2020-10-13T18:51:41.747 回答
0

按照@Petr 的建议，我从这里采用了一种可能的（库恩）算法。

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

于 2020-10-13T22:01:17.613 回答