How to determine best combinations from 2 lists

I'm looking for a way to make the best possible combination of people in groups. Let me sketch the situation.

Say we have persons A, B, C and D. Furthermore we have groups 1, 2, 3, 4 and 5. Both are examples and can be less or more. Each person gives a rating to each other person. So for example A rates B a 3, C a 2, and so on. Each person also rates each group. (Say ratings are 0-5). Now I need some sort of algorithm to distribute these people evenly over the开发者_JAVA百科 groups while keeping them as happy as possible (as in: They should be in a highrated group, with highrated people). Now I know it's not possible for the people to be in the best group (the one they rated a 5) but I need them to be in the best possible solution for the entire group.

I think this is a difficult question, and I would be happy if someone could direct me to some more information about this types of problems, or help me with the algo I'm looking for.

Thanks!

EDIT: I see a lot of great answers but this problem is too great for me too solve correctly. However, the answers posted so far give me a great starting point too look further into the subject. Thanks a lot already!

after establishing this is NP-Hard problem, I would suggest as a heuristical solution: Artificial Intelligence tools.

A possible approach is steepest ascent hill climbing [SAHC] first, we will define our utility function (let it be u). It can be the sum of total happiness in all groups.
next,we define our 'world': S is the group of all possible partitions.
for each legal partition s of 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 partition as starting point, denote it as s.
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 }
   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.

The problem is NP-hard: you can reduce from Maximum Triangle Packing, that is, finding at least k vertex-disjoint triangles in a graph, to the version where there are k groups of size 3, no one cares about which group he is in, and likes everyone for 0 or for 1. So even this very special case is hard.

To solve it, I would try using an ILP: have binary variables g_ik indicating that person i is in group k, with constraints to ensure a person is only in one group and a group has an appropriate size. Further, binary variables t_ijk that indicate that persons i and j are together in group k (ensured by t_ijk <= 0.5 g_ik + 0.5 g_jk) and binary variables t_ij that indicate that i and j are together in any group (ensured by t_ij <= sum_k t_ijk). You can then maximize the happiness function under these constraints.

This ILP has very many variables, but modern solvers are pretty good and this approach is very easy to implement.

This is an example of an optimization problem. It is a very well studied type of problems with very good methods to solve them. Read Programming Collective Intelligence which explains it much better than me.

Basically, there are three parts to any kind of optimization problem.

1. The input to the problem solving function.
2. The solution outputted by the problem solving function.
3. A scoring function that evaluates how optimal the solution is by scoring it.

Now the problem can be stated as finding the solution that produces the highest score. To do that, you first need to come up with a format to represent a possible solution that the scoring function can then score. Assuming 6 persons (0-5) and 3 groups (0-2), this python data structure would work and would be a possible solution:

output = [
    [0, 1],
    [2, 3],
    [4, 5]
    ]

Person 0 and 1 is put in group 0, person 2 and 3 in group 1 and so on. To score this solution, we need to know the input and the rules for calculating the output. The input could be represented by this data structure:

input = [
    [0, 4, 1, 3, 4, 1,  3, 1, 3],
    [5, 0, 1, 2, 1, 5,  5, 2, 4],
    [4, 1, 0, 1, 3, 2,  1, 1, 1],
    [2, 4, 1, 0, 5, 4,  2, 3, 4],
    [5, 5, 5, 5, 0, 5,  5, 5, 5],
    [1, 2, 1, 4, 3, 0,  4, 5, 1]
    ]

Each list in the list represents the rating the person gave. For example, in the first row, the person 0 gave rating 0 to person 0 (you can't rate yourself), 4 to person 1, 1 to person 2, 3 to 3, 4 to 4 and 1 to person 5. Then he or she rated the groups 0-2 3, 1 and 3 respectively.

So above is an example of a valid solution to the given input. How do we score it? That's not specified in the question, only that the "best" combination is desired therefore I'll arbitrarily decide that the score for a solution is the sum of each persons happiness. Each persons happiness is determined by adding his or her rating of the group with the average of the rating for each person in the group, excluding the person itself.

Here is the scoring function:

N_GROUPS = 3
N_PERSONS = 6
def score_solution(input, output):
    tot_score = 0
    for person, ratings in enumerate(input):
        # Check what group the person is a member of.
        for group, members in enumerate(output):
            if person in members:
                # Check what rating person gave the group.
                group_rating = ratings[N_PERSONS + group]

                # Check what rating the person gave the others.
                others = list(members)
                others.remove(person)
                if not others:
                    # protect against zero division
                    person_rating = 0
                else:
                    person_ratings = [ratings[o] for o in others]
                    person_rating = sum(person_ratings) / float(len(person_ratings))
                tot_score += group_rating + person_rating
    return tot_score

It should return a score of 37.0 for the given solution. Now what we'll do is to generate valid outputs while keeping track of which one is best until we are satisfied:

from random import choice
def gen_solution():
    groups = [[] for x in range(N_GROUPS)]
    for person in range(N_PERSONS):
        choice(groups).append(person)
    return groups

# Generate 10000 solutions
solutions = [gen_solution() for x in range(10000)]
# Score them
solutions = [(score_solution(input, sol), sol) for sol in solutions]
# Sort by score, take the best.
best_score, best_solution = sorted(solutions)[-1]
print 'The best solution is %s with score %.2f' % (best_solution, best_score)

Running this on my computer produces:

The best solution is [[0, 1], [3, 5], [2, 4]] with score 47.00

Obviously, you may think it is a really stupid idea to randomly just generate solutions to throw at the problem, and it is. There are much more sophisticated methods to generate solutions such as simulated annealing or genetic optimization. But they all build upon the same framework as given above.