0
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Thanks for the information. I did wonder if optimisation of "moves" was the way to go. $\endgroup$
    – Tom
    Feb 9, 2021 at 8:56
  • $\begingroup$ Sorry accidentally submitted. I've tackled this a different way and it seems to work. I'd be interested to hear your take on it. My algorithm is this: ``` sort the initial groups map by largest group first for each ordered group key, k; find 'best match' in new sets by jaccard similarity; add best set to result map with key k; take best set out of candidate pool; add remaining new sets to result map with random keys; ``` I'm not sure if this really is a solution or just works in a limited set of cases! Any thoughts? $\endgroup$
    – Tom
    Feb 9, 2021 at 9:03
  • $\begingroup$ To find the "best match", do you mean perform all pairwise comparisons between new and old groups? If so, what if there is a tie (one new group matches equally well to two or more initial groups)? What is an "ordered group key"? What does it mean to add a set to a result map "with random keys"? Whatever that means, it doesn't sound like something that guarantees an optimal solution to me. $\endgroup$ Feb 9, 2021 at 11:41
  • $\begingroup$ I've posted my code as an answer so it's more legible. I'm pretty certain it will break down in some cases, but I'm not sure which cases those are, and also unsure why exactly this seems to work! $\endgroup$
    – Tom
    Feb 9, 2021 at 11:48
  • $\begingroup$ I don't know the language your code is in, I don't understand why the input groups appears to be given as a string and an array instead of an array of arrays, you haven't explained what a "key" is, or what happens when there is a tie (ties are a common "smell" for algorithms that don't always optimal solutions), or why you would ever use "random" keys (another smell to say the least). I'm not very interested in looking for a proof of or counterexample to its correctness. Free LP solvers are available that will quickly give optimal solutions using my formulation; I suggest doing that. $\endgroup$ Feb 10, 2021 at 10:37
0
$\begingroup$

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)
}
```
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.