Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a situation where I have a pool of X people of different scores (ranks) S with game size N. How do I partition the pool into N sized games where the standard deviation of ranks for each games is minimized?

(quality of the game is inversely proportional to STD of ranks)

share|improve this question
Possible duplicate of… though a smaller subset. – The Communist Duck Dec 22 '10 at 15:47
@The Communist Duck I don't really want a framework. I'm looking to code it myself, so I need an algorithm (or heuristics). – Kendall Hopkins Dec 22 '10 at 16:05
It's not clear what you want to happen when N|X fails. Does N vary over some range? Can I make games with anywhere between 2 and N players? Are you looking to minimize the mean, total, or some other function of the standard deviations? – user744 Dec 23 '10 at 11:10
@Joe Wreschnig You can assume N % X == 0. Any N is an acceptable number, but N = 1 is the trivial case. – Kendall Hopkins Dec 23 '10 at 15:33

This is probably not mathematically optimal (optimality in this case reeks of NP to me, but I'm not certain), but assuming N is fixed and a unimodal, approximately normal S distribution you should be able to get something close to optimal just sorting by rank and slicing a group off every N players.

share|improve this answer

If your values for X and N are very large, it would probably make the most sence to keep the player list sorted by Rank such that you could always take the bottom N elements to create a group. This will front-load your computation time (keeping the list sorted every time you add a new item), in contrast with the above algorithm which would require execution every time a new group is to be created.

share|improve this answer
I've looked over this algorithm a bit and I can't understand the logic or it's result at all. Could you explain it a bit more? Why would I want a groupMembers filled with the index of players with the smallest rank? I've reworded the question, maybe that'll help make what I'm asking for more clear. – Kendall Hopkins Dec 23 '10 at 0:57
-1 - I think you're trying to do the same thing I suggested, but your actual code is nonsense. If players[0] has the smallest rank, your code provides garbage in groupMembers. If players[0] has the second-smallest, your code produces a group of N copies of the smallest group member. And so on. – user744 Dec 23 '10 at 11:20
After rereading the question and your updated explination, my code (even fixed) wouldn't have done what you want; that said, it is wrong, I'd copied it and removed some important bits. – Nate Dec 23 '10 at 16:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.