C# Algorithm to determine grouping of people based on a value

Question

I'm attempting to write an algorithm that creates groups of people based on their 'score'. A person has two paramaters, a name and a score. (The range of the score is between -10 and 10 but that's really not relevant) I'm looking to create groups with equal numbers of people (if possible based on the number of people presented) where the average score of the group members is the same (or very close to the same).

For example:

Group 1 (Average Score=2) -- John Doe, Score 2 -- Jane Doe, Score 7 -- Jack Black, Score -3

Group 2 (Average Score=2) -- Bobby Flay, Score 4 -- Cary Page, Score -3 -- Linus Tarval, Score 5

Answer 1

This smells like a variation of the classical Partition Problem, which is NP-Hard although some heuristics exists. You can have a loot at wikipedia page.. probably a greedy approach would work in your case.

You should try to fill your groups by choosing the right group to place a specific person, probably by starting with having them ordered by score.

Answer 2

This is a tough problem. The best you will probably do is a heuristic, but k-means is a good one: http://en.wikipedia.org/wiki/K-means_clustering