Is there a javascript function for finding the first set that contains one element each from a group of sets (if such a set exists for that group)?

Question

I'm trying to find a solution to a problem like the following, where I have three sets (technically arrays, but they will always be guaranteed not to have repeating elements and they will always have their elements in increasing order), and I need to determine the first set of numbers that will contain exactly one element from each set and have no overlapping values itself (if such a set of numbers can exist given the group of sets):

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

Before I jump into a solution that I suspect will have to be recursive and tax the ol' noodle considerably, I wanted to see if javascript had a built-in function to determine this sort of thing or if there was a straightforward approach that I'm missing. I've had no luck in my investigation of Set on MDN.

The solution will need to work for an arbitrary number of sets for which I'm seeking to find this "coalescing set".

Answer 1

This problem is obviously equivalent to finding a maximum cardinality matching in a bipartite graph. For each of sets create one vertex in one part of the graph, and for each item create one vertex in another part of the graph, and add edges between sets and its elements. After that you need to find a maximum cardinality matching and check that it contains all the vertices from the first part.

The algorithms for finding a maximum cardinality matching in a bipartite graph are widely known, see, e.g., the short list in the Wikipedia article linked above; and surely you can find many other resources on this topic. You might even try to find some Javascript library that implements one of these algorithms, although, obviously, the standard library of JS contains nothing of this sort.

This would find some coalescing set, but not specifically the first (and how do you define "first", by the way?); however, I think that a simple alteration of standard algorithms would allow you to find the lexicographically first matching.

Also note that not only your problem can be reduced to finding a maximum cardinality matching in a bipartite graph, but the reverse is also true. Namely, given some bipartite graph, just create your sets equal to adjacency lists of vertices from one part of the graph, and so you have reduced the problem of finding a maximum cardinality matching to your problem. So both problems are equivalent (and I would even say that they are exactly the same problem, as what you call "sets" are just adjacency lists of a bipartite graph), and hence you will most probably not be able to find any simpler algorithm that those already known for the matching problem. In particular, no greedy algorithm would work. (Or, well, maybe you will find a better algorithm, but this would be a really great scientific achievement.)

Answer 2

Following @Petr suggestion I took one of possible (Kuhn) algorithm from here.

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