Separate groups of people based on members

Question

I have groups of people. I need to move groups with at least one same member as far as possible from each other.

Example:

GroupA - John, Bob, Nick
GroupB - Jack, Nick
GroupC - Brian, Alex, Steve

As you can see GroupA and GroupB overlap(they both contain Nick) I need an algorithm to set groups as GroupA->GroupC->GroupB

Thank you

Answer 1

This problem does not have a unique or even meaningful solution if you have arbitrary groups. See for example:

GroupA = {Alice, Bob}
GroupB = {Bob, David}
GroupC = {David, Alice}

Answer 2

This depends on how you define the problem exactly -- with overlaps and costs and things.

This might reduces to Travelling salesman problem -- you can set edge weights as 0 if group i and j has nothing in common, and some function f(i,j) that depends on the number of common items between them. Then, you want a list that goes from one group to the last group, visiting each group once, minimizing some function of overlap.

You can probably reduce TSP to a version of this (really depending on how specific you mean by "farthest as possible", with regards to competing overlaps) similarly.

Unfortunately, this is NP-complete, which means you should start looking for something that's "good enough".