Need help finding/writing an algorithm to reassign items to groups with minimal changes

Question

I have some users in groups, like this (groups are letters, users are numbers):

{
  a: [1, 2, 3],
  b: [4],
  c: [5],
  d: [6],
  e: [7, 8, 9, 10]
}

I receive a new description of the grouping of these users like this:

[1, 2, 3, 4, 5, 6, 11],
[7, 8, 9, 10]

Now, I need to rearrange the users to minimize "changes", so in this case, they'd end up like this:

{
  a: [1, 2, 3, 4, 5, 6, 11],
  e: [7, 8, 9, 10]
}

A more nuanced example is this:

from:
{
  a: [1, 2, 3, 4, 5, 6]
  b: [7],
}

to:
[1, 2, 3, 7]
[4, 5, 6]

options:
{
  a: [1, 2, 3, 7],
  c: [4, 5, 6]
}
{
  a: [4, 5, 6]
  b: [1, 2, 3, 7], // THIS IS BEST
}

In this example, the second choice is best, because we move [1, 2, 3] to b rather than [4, 5, 6] to c and [7] to a.

I've been trying to come up with some heuristics, like starting with the largest invalidated group, then in that group, take the largest group that are still together after the change, and letting them keep their place.

That kind of thing seems to work, except in the second example, I can't think how to make it pick option 2 over option 1.

I'm wondering if this is a solved problem, if it can even be done without multiple passes and comparisons, and if I'm attacking this in a vaguely sensible way.

Any guidance would be greatly appreciated.

Answer 1

Every user either remains in their initial group, or moves to some other group for a cost of 1. So it suffices to look for a matching between new groups and old groups that maximises the number of users who don't need to move; subtracting the number of stationary people from the total number of people gives the number of people who need to move.

To do this, create an instance of the Assignment Problem, a.k.a. Maximum-weight Bipartite Matching, in which you have a vertex in A for every current group, a vertex in B for every new group, and an edge between every pair of vertices with weight equal to the number of users shared by the two groups (edges with weight 0 can be omitted). The goal is to find a matching -- a subset of edges, no two of which share an endpoint -- of maximum weight. To solve problem instances the size of your examples, trying all possibilities with brute force would be fine, but they can be solved more efficiently using the Hungarian Algorithm or linear programming, as described on the linked page.

Answer 2

I arrived at this, which passes my many tests but I'm not sure if it's guaranteed to give an optimal solution:

export function regroup<T>(
  before: Record<string, Array<T>>,
  after: Array<Array<T>>,
  generateKey: (items: Set<T>) => string
): Record<string, Array<T>> {
  // construct three working values - we will move groups from afterSets into
  // result, with the new key being the best match from the 'before' dictionary
  const beforeOrderedBySize = new Map(
    sortBy(
      Object.entries(before).map(([k, v]) => [k, toSet(v)]),
      ([, v]) => -v.size
    )
  )
  const afterSets = new Set(map(after, toSet))
  const result: Map<string, Set<T>> = new Map()

  // find best new set for each old set by key
  for (const [k, oldSet] of beforeOrderedBySize) {
    let highScore = 0
    let bestSet: Set<T> | null = null

    // find best match between old and new sets
    for (const newSet of afterSets) {
      const score = jaccardSimilarity(oldSet, newSet)
      if (score > highScore) {
        highScore = score
        bestSet = newSet

        // exact matches go straight through - (prevents extra loops)
        if (score === 1) break
      }
    }

    // move best set into result, removing from candidates
    if (bestSet) {
      result.set(k, bestSet)
      afterSets.delete(bestSet)
    }
  }

  // left over new groups need new keys
  for (const remainingGroup of afterSets) {
    result.set(generateKey(remainingGroup), remainingGroup)
  }

  return mapValues(Object.fromEntries(result.entries()), fromSet)
}
```