I have a situation where i have to create a C# routine which has the following logic to take a list of people and divide them into 2 teams based on preferences:

1. I have an array of 20 names:

   var names = new List(){"Joe", "Bill", "Scott", "Jonathan", . . .}

2. Each name can give 0 to 3 preferences, so for each name, I have is an array of 0 to 3 length and is an array of strings with other names in the list (they are people they want to be on their team)

3. I now need to solve for taking the list of 20 people and dividing them into 2 teams and creating the teams (sub lists) based on optimizing for people's preferences. So each person should get AT LEAST one person that they included in their preference on their team (if mathematically possible). There is no priority of one person above anyone else, just trying to optimize for the top number of matches.

I can convert the string lists into a list of objects

 List<Person> list = CreateList(array) 

where Person class is the following

  public class Person
  {
      public string Name;
      public List<Person> Preferences;
  }

but now i am trying to figure out how to use this data structure to generate the 2 teams where i end up with 2 lists of teams that are set of 10 people.

CodePudding user response：

The optimal flow method can solve your problem - maximizing flow in a graph which branches capacity express preferences. There is a N^3 algorithm.

See here for an example : Algorithm for optimal matching with choices and ranking

CodePudding user response：

Instead of setting up an adjacency matrix and trying to extract some meaningful vector solution via linear algebra, I think you might get some mileage out of an iterative "team captain" type model.

I would start by representing each individual's preferences as a row vector, mimicking the rows of an adjacency matrix.

For ease of explanation, I'll use an example with 4 people: A, B, C, and D. A and D want to be together, B wants to be with C, and C wants to be with A.

The rows of the adjacency matrix are [1,0,0,1],[0,1,1,0],[1,0,1,0],[1,0,0,1]. So I would carry on representing each individual as their row in the adjacency matrix. A is [1,0,0,1], B is [0,1,1,0], C is [1,0,1,0], and D is [1,0,0,1].

Now I would create team captains. I'm going to look for two vectors whose dot product is minimal. A zero dot product is not guaranteed to exist by your requirements. For instance, everyone could want to be with one particular individual. But you can still find two vectors whose dot product is minimal, and entirely orthogonal is likely in practice.

Now make those two people team captains. In this example, that means A=[1,0,0,1] and B=[0,1,1,0] are viable team captains.

Now iteratively allow them to start picking their teams. A can find his optimal new member by taking dot products with C, and D, and observing D yields the maximum dot product, resulting in the teams {A,D}, {B,C}.

Of course, in your case, it doesn't stop there. So let's consider what would happen if there were also an E, F, G, and H waiting to get picked. In that case, the team {A,D} would multiply the (column) matrix [A][D] with the (column) vectors [E],[F],[G], and [H], and see which product has maximal norm, selecting it and allowing team {B,C} to select its newest member through the same process: max{norm([B][C]*[candidate])}.