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.