- Edited
@arithma: as I mentioned that was an an initial solution for the specific 10 player scenario. On the other hand here is another general solution that does not use any arrays:
* I used a recursive technique to simulate the nested loops while keeping that number of loops dynamic (using a depth parameter)
* I am trying to find the closest sum to half the sum of all player ratings, if I find an exact match I quit, this means that only one solution is considered
* I am using a Fold method that will rearrange the players according to their ratings. The rearrangement can be visualized as a sorted list being folded in half, thus the min and max are next to each other, then the first number greater than min is adjacent to the first number less than max and so on... The benefit of using this method is not certain to me yet, just a shot in the dark...
* I was not able to bench mark this and get consistent times since sometimes a 50 player scenario would be solved in less than a second and in other times it takes about 2 minutes. Feel free to benchmark it and post some results if you want .
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace SplitTeams
{
class Program
{
class Player
{
public string Name { get; set; }
public int Rating { get; set; }
}
class Match : List<int>
{
public int Sum { get; set; }
public Match() { }
public Match(Match from)
: base(from)
{
this.Sum = from.Sum;
}
}
private static int _TotalPlayers;
private static Random rnd = new Random(DateTime.Now.Millisecond);
private static float _Half;
private static Player[] _Players;
private static bool _Finished = false;
private static void loop(ref Match bestMatch, Match current, int depth, int start)
{
if (depth == (_TotalPlayers / 2) - 1)
{
current.Sum = 0;
for (int i = 0; i < current.Count; i++)
current.Sum += _Players[current[i]].Rating;
if (Math.Abs(bestMatch.Sum - _Half) > Math.Abs(current.Sum - _Half))
{
bestMatch = new Match(current);
_Finished = bestMatch.Sum == _Half;
}
}
else
{
//using a copy so we don't modify current and it retains same values as when it was passed as parameter
Match copy = new Match(current);
for (copy[depth] = depth >= 1 ? copy[depth - 1] + 1 : 0; !_Finished && copy[depth] < _TotalPlayers; copy[depth]++)
{
bool duplicate = false;
int val = copy[depth];
for (int i = 0; i < copy.Count && !(duplicate = (i != depth && copy[i] == val)); i++) ;
if (!duplicate)
loop(ref bestMatch, copy, depth + 1, start + 1);
}
}
}
private static void Split(Player[] team1, Player[] team2)
{
Match current = new Match(), match = new Match();
//initialize
for (int i = 0; i < _TotalPlayers / 2; i++)
{
match.Add(i);
current.Add(i);
}
_Half = ((float)_Players.Sum(x => x.Rating)) / 2;
_Players = Fold(_Players);
loop(ref match, current, 0, 0);
int team1Counter = 0, team2Counter = 0;
for (int i = 0; i < _Players.Length; i++)
{
if (match.Contains(i))
team1[team1Counter++] = _Players[i];
else
team2[team2Counter++] = _Players[i];
}
}
private static Player[] Fold(Player[] players)
{
players = players.OrderBy(x => x.Rating).ToArray();
int foldedIndex = 0;
bool rightLeft = false;
Player[] folded = new Player[players.Length];
for (int i = 0; i < players.Length/2; i+=(rightLeft ? 1 : 0), rightLeft = !rightLeft)
{
folded[foldedIndex++] = rightLeft ? players[i] : players[players.Length - i - 1];
}
return folded;
}
private static Player[] GeneratePlayers()
{
Player[] result = new Player[_TotalPlayers];
for (int i = 0; i < result.Length; i++)
result[i] = new Player { Name = "Player" + i.ToString(), Rating = rnd.Next(2000) };
return result;
}
static void Main(string[] args)
{
_TotalPlayers = 10;
if (args.Length > 0)
int.TryParse(args[0], out _TotalPlayers);
if (_TotalPlayers % 2 != 0)
throw new Exception("Invalid PLAYER_COUNT, must be even.");
DateTime start = DateTime.Now;
_Players = GeneratePlayers();
DateTime end = DateTime.Now;
TimeSpan diff = end.Subtract(start);
Console.WriteLine(string.Format("Generated {0} players in {1} milliseconds", _TotalPlayers, diff.TotalMilliseconds));
Player[] team1 = new Player[_TotalPlayers / 2];
Player[] team2 = new Player[_TotalPlayers / 2];
start = DateTime.Now;
Split(team1, team2);
end = DateTime.Now;
diff = end.Subtract(start);
Console.WriteLine(string.Format("Split {0} players into 2 {1} player teams in {2} milliseconds.", _TotalPlayers, _TotalPlayers / 2, diff.TotalMilliseconds));
float sum1 = team1.Sum(x => x.Rating);
float sum2 = team2.Sum(x => x.Rating);
float perc1 = (sum1 * 100) / (sum1 + sum2);
float perc2 = (sum2 * 100) / (sum1 + sum2);
Console.WriteLine(string.Format("Team 1: ({0:f2}%)", perc1));
foreach (Player p in team1)
Console.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
Console.WriteLine(string.Format("Team 2: ({0:f2}%)", perc2));
foreach (Player p in team2)
Console.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
Console.Read();
}
}
}* I used a recursive technique to simulate the nested loops while keeping that number of loops dynamic (using a depth parameter)
* I am trying to find the closest sum to half the sum of all player ratings, if I find an exact match I quit, this means that only one solution is considered
* I am using a Fold method that will rearrange the players according to their ratings. The rearrangement can be visualized as a sorted list being folded in half, thus the min and max are next to each other, then the first number greater than min is adjacent to the first number less than max and so on... The benefit of using this method is not certain to me yet, just a shot in the dark...
* I was not able to bench mark this and get consistent times since sometimes a 50 player scenario would be solved in less than a second and in other times it takes about 2 minutes. Feel free to benchmark it and post some results if you want .
