C# – Algorithm for Generating Random Teams Based on Skill Level

algorithmsc

I'm looking for some assistance and ideas for developing an algorithm for choosing random soccer teams based on the skill levels of the participating players.
What I have so far is a list of particpating players with arbitrary skill levels between 1 and 100. e.g.

PlayerA: 30,
PlayerB: 45,
PlayerC: 50,
PlayerD: 55,
PlayerE: 30,
PlayerF: 20,
PlayerG: 75,
PlayerH: 75

I'd like the option of being able to choose random teams, but efficiently running it again to offer different results if the teams just don't look fair (even if on paper, the assigned skill levels match).

I've already coded an example which creates all possible combinations of teams and orders them by fairest first, so that efficiently creates the functionality that allows the person to hit the "randomise" button again and instantly display new teams. However, this is only suitable for teams of 7 per side (maybe 8) as there are just too many combinations after that and it takes too long to process.

Can anyone suggest a better way of doing this for more than 8 players? I've tried the option which mimics the old school yard method of picking players by taking the two best players as the captains and then each player taking the best of who is left until everyone is picked, but then i was stumped if those teams weren't acceptable and they wanted an option to randomise again.

Many thanks – i'm coding this in C# but the language is probably less important than the theory.

Best Answer

I suggest a time-boxed approach.

  1. Generate two random teams using whatever method you have been using
  2. Compute the total skill of both teams, and take the difference
  3. If the difference is 0, your teams are perfectly balanced. Exit.
  4. Trade two random team members and recompute the total skill and difference.
  5. If the difference is smaller, proceed with the new teams. Otherwise keep the old ones.
  6. Repeat steps 3, 4 and 5 for a fixed number of iterations or a fixed duration of execution, e.g. keep trading for three seconds or a thousand iterations.
  7. If you keep getting the same team composition, reduce the number of iterations. If you keep getting very unbalanced teams, increase it.
Related Topic