Friends selection algorithm

In a .net project we have a group of 200 people of two types, lets say x and y, who need to be separated into groups of 7 or 8.

We have a web page where the people write other members they want to be in a group with. Each person builds a list of wanted members.

After this, there should be an algorithm to buil开发者_StackOverflowd the 7-8 member groups considering the peoples ratings, and the following condition: each group has at least 2 people of each type (x/y).

I'm pretty sure there must be a well known algorithm similar to this but didn't find one. Anyone knows how to do it?

---

this problem smells NP-Hard, so I suggest using Artificial Intelligence tools.

A possible approach is steepest ascent hill climbing [SAHC] first, we will define our utility function (let it be u) as mentioned in the comments to the question. [sum of friends in group for each user]. let's define u(illegal) = -1 for illegal solution.
next,we define our 'world': S is the group of all possible solutions].
for each solution in S we define:
next(s)={all possibilities moving one person to a different group}

all we have to do now is run SAHC with random restarts:

1. best<- -INFINITY 
2. while there is more time
3. choose a random legal solution
4. NEXT <- next(s)
5. if max{ U(NEXT) } < u(s): //s is the top of the hill
   5.1. if u(s) > best: best <- u(s) //if s is better then the previous result - store it.
   5.2. go to 2. //restart the hill climbing from a different random point.
6. else:
   6.1. s <- max{ NEXT } //climb on the steepest hill.
   6.2. goto 4.
7. return best //when out of time, return the best solution found so far.

It is anytime algorithm, meaning it will get a better result as you give it more time to run, and eventually [at time infinity] it will find the optimal result.