2
\$\begingroup\$

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)

\$\endgroup\$
4
  • \$\begingroup\$ Possible duplicate of gamedev.stackexchange.com/questions/464/… though a smaller subset. \$\endgroup\$ Commented Dec 22, 2010 at 15:47
  • \$\begingroup\$ @The Communist Duck I don't really want a framework. I'm looking to code it myself, so I need an algorithm (or heuristics). \$\endgroup\$ Commented Dec 22, 2010 at 16:05
  • \$\begingroup\$ 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? \$\endgroup\$
    – user744
    Commented Dec 23, 2010 at 11:10
  • \$\begingroup\$ @Joe Wreschnig You can assume N % X == 0. Any N is an acceptable number, but N = 1 is the trivial case. \$\endgroup\$ Commented Dec 23, 2010 at 15:33

2 Answers 2

1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Dec 23, 2010 at 0:57
  • \$\begingroup\$ -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. \$\endgroup\$
    – user744
    Commented Dec 23, 2010 at 11:20
  • \$\begingroup\$ 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. \$\endgroup\$
    – Nate
    Commented Dec 23, 2010 at 16:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .