• Coding
  • Exercise - Team Balancing

@arithma: OK, I'll take that and I will raise you. Added the Fold method again (since a sequence is a worst case scenario) which I think (did not check your code thoroughly) is equivalent to your shuffle, and voiala:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.IO;

namespace SplitTeams
{
    class Program
    {
        class Player
        {
            public string Name { get; set; }
            public int Rating { get; set; }
        }

        private static int _TotalPlayers;
        private static Random rnd = new Random(DateTime.Now.Millisecond);
        private static Player[] _Players;


        private static bool FindSwappables(Player[] team1, Player[] team2, int diff, out int player1, out int player2)
        {
            player1 = 0;
            player2 = 0;
            int? maxDiff = null;
            double halfDiff = Math.Abs(Math.Ceiling((float)diff / 2));
            for (int i = 0; i < team1.Length; i++)
            {
                for (int j = 0; j < team2.Length; j++)
                {
                    int currentDiff = team1[i].Rating - team2[j].Rating;
                    if (currentDiff > 0 && diff > 0 || currentDiff < 0 && diff < 0)//elligible swap (same sign)
                    {
                        currentDiff = Math.Abs(currentDiff);
                        if (currentDiff <= halfDiff && (!maxDiff.HasValue || currentDiff > maxDiff))
                        {
                            maxDiff = currentDiff;
                            player1 = i;
                            player2 = j;
                        }
                    }
                }
            }
            return maxDiff != null;
        }

        private static void Cut(Player[] team1, Player[] team2)
        {
            for (int i = 0; i < _Players.Length / 2; i++)
                team1[i] = _Players[i];
            for (int i = _Players.Length / 2, counter = 0; i < _Players.Length; i++, counter++)
                team2[counter] = _Players[i];
        }

        private static void Swap(Player[] team1, Player[] team2, int team1Index, int team2Index, ref int sum1, ref int sum2)
        {
            Player temp = team1[team1Index];
            team1[team1Index] = team2[team2Index];
            team2[team2Index] = temp;
            sum1 += team1[team1Index].Rating - team2[team2Index].Rating;
            sum2 += team2[team2Index].Rating - team1[team1Index].Rating;
        }
        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 void Split(Player[] team1, Player[] team2)
        {
            _Players = Fold(_Players);
            Cut(team1, team2);
            int s1, s2, sum1, sum2;
            sum1 = team1.Sum(x => x.Rating);
            sum2 = team2.Sum(x => x.Rating);
            int diff = sum1 - sum2;
            while (diff != 0 && FindSwappables(team1, team2, diff, out s1, out s2))
            {
                Swap(team1, team2, s1, s2, ref sum1, ref sum2);
                diff = sum1 - sum2;
            }
        }

        #region Util

        private static void GeneratePlayers()
        {
            DateTime start = DateTime.Now;
            _Players = new Player[_TotalPlayers];
            for (int i = 0; i < _Players.Length; i++)
                _Players[i] = new Player { Name = "Player" + i.ToString(), Rating = rnd.Next(2000) };
            DateTime end = DateTime.Now;
            TimeSpan diff = end.Subtract(start);
            Console.WriteLine(string.Format("Generated {0} players in {1} milliseconds", _TotalPlayers, diff.TotalMilliseconds));
        }

        private static void SplitAndReporttoConsole()
        {
            Player[] team1 = new Player[_TotalPlayers / 2];
            Player[] team2 = new Player[_TotalPlayers / 2];
            DateTime start = DateTime.Now;
            Split(team1, team2);
            DateTime end = DateTime.Now;
            TimeSpan 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));
        }
        private static void SplitAndReportToFile()
        {
            FileInfo fi = new FileInfo("C:\\output.txt");
            FileStream fs = null;
            if (!fi.Exists)
                fs = new FileStream("C:\\output.txt", FileMode.Create);
            else
                fs = File.Open("C:\\output.txt", FileMode.Truncate);
            StreamWriter sw = new StreamWriter(fs);
            
            Player[] team1 = new Player[_TotalPlayers / 2];
            Player[] team2 = new Player[_TotalPlayers / 2];
            DateTime start = DateTime.Now;
            Split(team1, team2);
            DateTime end = DateTime.Now;
            TimeSpan 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);
            sw.WriteLine(string.Format("Team 1: ({0:f2}%)", perc1));
            foreach (Player p in team1)
                sw.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
            sw.WriteLine(string.Format("Team 2: ({0:f2}%)", perc2));
            foreach (Player p in team2)
                sw.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
            sw.Close();
            fs.Close();
        }
        private static void InsureTotalPlayers(string[] args)
        {
            if (args.Length > 0)
                int.TryParse(args[0], out _TotalPlayers);
            if (_TotalPlayers % 2 != 0)
                throw new Exception("Invalid PLAYER_COUNT, must be even.");
        }

        #endregion

        static void Main(string[] args)
        {
         /*   _Players = new Player[]
            {
            new Player{Name="A", Rating=500},
            new Player{Name="A", Rating=1},
            new Player{Name="A", Rating=233},
            new Player{Name="A", Rating=10},
            new Player{Name="A", Rating=71},
            new Player{Name="A", Rating=112},
            new Player{Name="A", Rating=9},
            new Player{Name="A", Rating=46}
        };*/
            _TotalPlayers = 10000;
            
            InsureTotalPlayers(args);
            _Players = new Player[_TotalPlayers];
            for (int i = 0; i < _TotalPlayers; i++)
                _Players[i] = new Player { Name = i.ToString(), Rating = i };
            //GeneratePlayers();
            SplitAndReportToFile();
            Console.Write("Press any key to exit.");
            Console.Read();
        }
    }
}
and check the time :
Split 10000 players into 2 5000 player teams in 12.6953 milliseconds.
That is expected but what about a random input instead of a sequence:
Split 10000 players into 2 5000 player teams in 127.9297 milliseconds.
Beat that !!! ;)
LOL, this is hilarious. My fiance will beat me with a stick for playing away for so long. I'll see into this at night, expect some classic ass beating :P
arithma wroteLOL, this is hilarious. My fiance will beat me with a stick for playing away for so long. I'll see into this at night, expect some classic ass beating :P
LOL, I will be waiting ;)
In most games, the array of teams is already sorted according to ratings by the server (when a team is selected) this minimizes time on the server.
anyways greed is good :)
#include <iostream>
#include <vector>
using namespace std;


void main(void){
	vector<int> a;
    int const K = 10000;
    for(int i = 0; i < K; i++){
        a.push_back(rand());
    }
	vector<int> TL;
	vector<int> TR;
	TL.push_back(a[0]);
	TR.push_back(a[1]);
	size_t idx = 2;
	int maxSum = a[0];
	int minSum = a[1];
	vector<int> *currentMax = &TL;
	vector<int> *currentMin = &TR;
	while(idx < a.size()){
		(*currentMin).push_back(a[idx]);
		minSum += a[idx];
		if(minSum > maxSum){
			int tmpSum = minSum;
			minSum = maxSum;
			maxSum = tmpSum;
			vector<int> *tmp = currentMin;
			currentMin = currentMax;
			currentMax = tmp;
		}

		idx++;
	}
	cout<<minSum<<endl<<maxSum<<endl;
	cout<<(*currentMin).size()<<endl<<(*currentMax).size()<<endl;
}
Edit: forgot to restrict team members to be equal , might do it later
(rating is always positive).
#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
using namespace std;


void main(void){
	vector<int> a;
    int const K = 1999500;
    for(int i = 0; i < K; i++){
        a.push_back(rand());
    }
	sort(a.begin(),a.end());
	clock_t start;
	start = clock();

	vector<int> TL;
	vector<int> TR;
	TL.push_back(a[0]);
	TR.push_back(a[1]);
	size_t idx = 2;
	unsigned int maxSum = a[0];
	unsigned int minSum = a[1];
	vector<int> *currentMax = &TL;
	vector<int> *currentMin = &TR;
	while(idx < a.size()){
		(*currentMin).push_back(a[idx]);
		minSum += a[idx];
		if(minSum > maxSum || (*currentMin).size() > (*currentMax).size()){
			int tmpSum = minSum;
			minSum = maxSum;
			maxSum = tmpSum;
			vector<int> *tmp = currentMin;
			currentMin = currentMax;
			currentMax = tmp;
		}

		idx++;
	}
	cout<<"Execution Time: "<<( double(clock() - start)/CLOCKS_PER_SEC )<<endl;


	cout<<minSum<<endl<<maxSum<<endl;
	cout<<(*currentMin).size()<<endl<<(*currentMax).size()<<endl;
}
Execution Time: 0.038
3505837259
3505853690
999750
999750
ZeRaW wrote(rating is always positive).
#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
using namespace std;


void main(void){
	vector<int> a;
    int const K = 1999500;
    for(int i = 0; i < K; i++){
        a.push_back(rand());
    }
	sort(a.begin(),a.end());
	clock_t start;
	start = clock();

	vector<int> TL;
	vector<int> TR;
	TL.push_back(a[0]);
	TR.push_back(a[1]);
	size_t idx = 2;
	unsigned int maxSum = a[0];
	unsigned int minSum = a[1];
	vector<int> *currentMax = &TL;
	vector<int> *currentMin = &TR;
	while(idx < a.size()){
		(*currentMin).push_back(a[idx]);
		minSum += a[idx];
		if(minSum > maxSum || (*currentMin).size() > (*currentMax).size()){
			int tmpSum = minSum;
			minSum = maxSum;
			maxSum = tmpSum;
			vector<int> *tmp = currentMin;
			currentMin = currentMax;
			currentMax = tmp;
		}

		idx++;
	}
	cout<<"Execution Time: "<<( double(clock() - start)/CLOCKS_PER_SEC )<<endl;


	cout<<minSum<<endl<<maxSum<<endl;
	cout<<(*currentMin).size()<<endl<<(*currentMax).size()<<endl;
}
Execution Time: 0.038
3505837259
3505853690
999750
999750
From skimming through your implementation, I think that your test input would result in distributing the sorted list among the 2 list in an alternating manner, which would cause the 2 lists to reach the final state automatically and without further processing, and this might also get you a clear 50/50 cut. To really test your code, generate random data instead of a simple sequence.
You are right, if the array is sorted just add one to the first team, then another to the second team and you will get 50/50 with closest ratings.
In any case as I said before, in real-time you need to go to the simplest way.
Second implementation is wrong and my battery died, a simpler one:
#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
using namespace std;


void main(void){
	vector<int> a;
    int const K = 1999500;
    for(int i = 0; i < K; i++){
		srand(i);
        a.push_back(rand());
    }
	sort(a.begin(),a.end());
	clock_t start;
	start = clock();

	vector<int> TL;
	vector<int> TR;
	TL.push_back(a[0]);
	TR.push_back(a[1]);
	size_t idx = 2;
	unsigned int maxSum = a[0];
	unsigned int minSum = a[1];
	vector<int> *currentMax = &TL;
	vector<int> *currentMin = &TR;
	while(idx < a.size()){
		(*currentMin).push_back(a[idx]);
		minSum += a[idx];
		int tmpSum = minSum;
		minSum = maxSum;
		maxSum = tmpSum;
		vector<int> *tmp = currentMin;
		currentMin = currentMax;
		currentMax = tmp;
	

		idx++;
	}
	cout<<"Execution Time: "<<( double(clock() - start)/CLOCKS_PER_SEC )<<endl;


	cout<<minSum<<endl<<maxSum<<endl;
	cout<<(*currentMin).size()<<endl<<(*currentMax).size()<<endl;
}
I know I thought the last one was my best, well this is MUCH more performant taking advantage of multiple shortcuts and also has a progress indication.
To note about this:
* the list is cut in half into 2 sorted lists using the Cut method
* the FindSwappables method loops through the players in team 1 trying to find the best player_team1/player_team2 pair that if swapped will get us closer to a solution (less difference between the sums of the ratings of the 2 team)
* the method FindPlayerToSwapWith finds the best choice from team 2 to swap with a preselected player from team 1. This makes use of the fact that the team2 list is sorted and does a binary search to try and locate a player.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.IO;

namespace SplitTeams
{
    class Program
    {
        class Player
        {
            public string Name { get; set; }
            public long Rating { get; set; }
        }

        private static int _TotalPlayers;
        private static Random rnd = new Random(DateTime.Now.Millisecond);
        private static Player[] _Players;

        private static bool FindSwappables(Player[] team1, Player[] team2, long diff, out int player1, out int player2)
        {
            player1 = 0;
            player2 = 0;
            long? maxDiff = null;
            long halfDiff = Convert.ToInt64(Math.Abs(Math.Ceiling((double)diff / 2)));
            for (int i = 0; i < team1.Length; i++)
            {
                long rating = team1[i].Rating;
                int? foundIndex = null;
                if (diff > 0) //S1 > S2
                    foundIndex = FindPlayerToSwapWith(team2, 0, team2.Length - 1, rating - (halfDiff > rating ? 0 : halfDiff), null, rating);
                else
                    foundIndex = FindPlayerToSwapWith(team2, 0, team2.Length - 1, team1[i].Rating + halfDiff, rating, null);

                if (foundIndex.HasValue)
                {
                    long currentDiff = team1[i].Rating - team2[foundIndex.Value].Rating;
                    currentDiff = Math.Abs(currentDiff);
                    if (currentDiff != 0 && currentDiff <= halfDiff && (!maxDiff.HasValue || currentDiff > maxDiff))
                    {
                        maxDiff = currentDiff;
                        player1 = i;
                        player2 = foundIndex.Value;
                    }
                }
            }
            return maxDiff != null;
        }
        
        private static int? FindPlayerToSwapWith(Player[] list, int start, int end, long value, long? lowerBound, long? upperBound)
        {
            int diff = end - start;
            bool acceptHigher = lowerBound.HasValue;
            bool acceptLower = upperBound.HasValue;
            if (value == list[start].Rating || (acceptHigher && lowerBound < list[start].Rating)) return start;
            if(value == list[end].Rating || (acceptLower && upperBound > list[end].Rating)) return end;
            if (acceptLower && diff == 1) return start;
            if (acceptHigher && diff == 1) return end;
            if (end <= start || value < list[start].Rating || value > list[end].Rating) return null;
            if (list[start + diff / 2].Rating > value)
                end = start + diff / 2;
            else
                start = start + diff / 2;
            return FindPlayerToSwapWith(list, start, end, value, lowerBound, upperBound);
        }
        
        private static void Cut(Player[] team1, Player[] team2)
        {
            for (int i = 0; i < _Players.Length / 2; i++)
                team1[i] = _Players[i];
            for (int i = _Players.Length / 2, counter = 0; i < _Players.Length; i++, counter++)
                team2[counter] = _Players[i];
            team1 = team1.OrderBy(x => x.Rating).ToArray();
            team2 = team2.OrderBy(x => x.Rating).ToArray();
        }

        private static void Swap(Player[] team1, Player[] team2, int team1Index, int team2Index, ref long sum1, ref long sum2)
        {
            Player temp = team1[team1Index];
            team1[team1Index] = team2[team2Index];
            team2[team2Index] = temp;
            sum1 += team1[team1Index].Rating - team2[team2Index].Rating;
            sum2 += team2[team2Index].Rating - team1[team1Index].Rating;
        }
        
        private static void Split(Player[] team1, Player[] team2)
        {
            //_Players = Fold(_Players);
            Cut(team1, team2);
            int s1, s2; long sum1, sum2, startDiff;
            sum1 = team1.Sum(x => x.Rating);
            sum2 = team2.Sum(x => x.Rating);
            
            long diff = sum1 - sum2;
            startDiff = diff;
            double percentageComplete = 0, previousPercentage = 0;
            Console.WriteLine();
            while (diff != 0 && FindSwappables(team1, team2, diff, out s1, out s2))
            {
                Swap(team1, team2, s1, s2, ref sum1, ref sum2);
                diff = sum1 - sum2;
                
                percentageComplete = (1 - (double)diff / (double)startDiff) * 100;
                if (percentageComplete - previousPercentage >= 1)
                {
                    previousPercentage = percentageComplete;
                    Console.Write(string.Format("\r{0:f2}%", percentageComplete));
                }
            }
            Console.WriteLine("\r100%");
        }

        #region Util

        private static void GeneratePlayers()
        {
            DateTime start = DateTime.Now;
            _Players = new Player[_TotalPlayers];
            for (int i = 0; i < _Players.Length; i++)
                _Players[i] = new Player { Name = "Player" + i.ToString(), Rating = rnd.Next(5000) };
            DateTime end = DateTime.Now;
            TimeSpan diff = end.Subtract(start);
            Console.WriteLine(string.Format("Generated {0} players in {1} milliseconds", _TotalPlayers, diff.TotalMilliseconds));
        }

        private static void SplitAndReporttoConsole()
        {
            Player[] team1 = new Player[_TotalPlayers / 2];
            Player[] team2 = new Player[_TotalPlayers / 2];
            DateTime start = DateTime.Now;
            Split(team1, team2);
            DateTime end = DateTime.Now;
            TimeSpan 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));
        }
        
        private static void SplitAndReportToFile()
        {
            FileInfo fi = new FileInfo("C:\\output.txt");
            FileStream fs = null;
            if (!fi.Exists)
                fs = new FileStream("C:\\output.txt", FileMode.Create);
            else
                fs = File.Open("C:\\output.txt", FileMode.Truncate);
            StreamWriter sw = new StreamWriter(fs);

            Player[] team1 = new Player[_TotalPlayers / 2];
            Player[] team2 = new Player[_TotalPlayers / 2];
            DateTime start = DateTime.Now;
            Split(team1, team2);
            DateTime end = DateTime.Now;
            TimeSpan 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);
            sw.WriteLine(string.Format("Team 1: ({0:f2}%)", perc1));
            foreach (Player p in team1)
                sw.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
            sw.WriteLine(string.Format("Team 2: ({0:f2}%)", perc2));
            foreach (Player p in team2)
                sw.WriteLine(string.Format("Name: {0}, Rating: {1}", p.Name, p.Rating));
            sw.Close();
            fs.Close();
        }
        
        private static void InsureTotalPlayers(string[] args)
        {
            if (args.Length > 0)
                int.TryParse(args[0], out _TotalPlayers);
            if (_TotalPlayers % 2 != 0)
                throw new Exception("Invalid PLAYER_COUNT, must be even.");
        }

        #endregion

        static void Main(string[] args)
        {
            /*   _Players = new Player[]
               {
               new Player{Name="A", Rating=500},
               new Player{Name="A", Rating=1},
               new Player{Name="A", Rating=233},
               new Player{Name="A", Rating=10},
               new Player{Name="A", Rating=71},
               new Player{Name="A", Rating=112},
               new Player{Name="A", Rating=9},
               new Player{Name="A", Rating=46}
           };*/
            _TotalPlayers = 1000000;

            InsureTotalPlayers(args);
            //_Players = new Player[_TotalPlayers];
            //for (int i = 0; i < _TotalPlayers; i++)
            //    _Players[i] = new Player { Name = i.ToString(), Rating = i };
            GeneratePlayers();
            SplitAndReportToFile();
            Console.Write("Press any key to exit.");
            Console.Read();
        }
    }
}
1 million players, valid ratings 0 -> 5000:
Generated 1000000 players in 954.1016 milliseconds

100%
Split 1000000 players into 2 500000 player teams in 47632.8125 milliseconds.
that yielded an exact 50/50 split.
Random numbers generated using rand from stdlib (0 to 0x7FFF).
For 10,000 Numbers
81107087 - 81107086 = 1
5572*1000000/2337939 = 2383microseconds
For 100,000 Numbers, for one of the worst cases.
819261805 - 819261804 = 1
74555*1000000/2337939 = 31889microseconds
However, when I used a Mersene Twister, and masked by 0xFFFFFFFFFFFF (48bits on) I started getting results such as there:
7045553622973428157 - 7045553622973352279 = 75878
141490*1000000/2337939 = 60519microseconds
I think the results deteriorate for a very important reason: There's less possibilities for the algorithm to find a decent pair to swap as to minimize the difference to zero, which means we won't have as much reassurance that this combination the swapping ended with is optimal.

@MSD: Your code does not return no matter what I tried with 100,000 values. Note that you must use longs instead of integers to handle such huge sums decently.
You can find a C, C++, C# Mersene Twister here: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/C-LANG/c-lang.html
I am using the C version from my C++ code by including and using extern "C".
@arithma, did you check the latest edition? It has long and a bunch of other goodies ;)
My algorithm is solving the million number problem for a range from [0, 32767) in under 100milliseconds. The reason that our algorithms are doing such a good job is that the problem has become much easier when there's a plethora of options to pick from. For example, my algorithm resolves the just mentioned range and count in under 10 swaps (usually a single swap or 5 swaps would suffice apart from the rare or the unobserved).

With this description of your algorithm, I think our methods have converged. We need to break a new frontier. I suggest we deal with 48 bit random numbers using a MerseneTwister. We'll deal with counts up to 1,000,000 for now. We'll compare algorithms based on Random Number seeds. We can verify things by binary blobs of the partitioned arrays.

It's probably to the best if we play cool about this problem now, I don't want this obsession to take over my life.

BTW: I already have a head start with the techniques, and by playing with the already linked to mersene twister.

PS: You can start experimenting immediately with [0,5000) rank range with a 100 elements. The behavior will be apparent to you: You can't be sure whether your results are optimal or not when the range with respect to the count of elements is large. I believe this is the core of the problem that I was bouncing around explaining with theory earlier. No, we should rather start here. 100 ranks, ranging from 0 to 5000. No need for extra libraries. That will come later. We should come up with a technique to generate the same sequences from the same seed, so that we can communicate better, and race, without having to expose our techniques. We can of course share all the code towards closing the problem and declaring a bad ass winner and a sour ass loser :P

Cheers.
Arithma and MSD...
Just out of curiosity, Why do you both always tend to complicate things this much ?
Georges wroteArithma and MSD...
Just out of curiosity, Why do you both always tend to complicate things this much ?
Too much free time?
Georges wroteArithma and MSD...
Just out of curiosity, Why do you both always tend to complicate things this much ?
Because optimization is exactly the point of these exercises. Going for simple solutions like the quadratic one, is not at all the most interesting part of such programming.
We wish it's quadratic. It's actually exponential in complexity. However there are tricks that you can do, but you can't be sure that your result is optimal.

@Georges: I do not think we complicated this problem. I did however push this conversation into something collaborative, competitive and exciting at the same time.

@ZeRaW: Yes, I do have about 10 hours of free time a day, be it a work day or not.

Anyway, here's the 64-bit Mersene Twister ported to C#. I ported it based on a 32 bit implementation in C#, and matched it with the C implementation I am using. You're welcome.

main.cs
using System;

namespace MerseneTwisterTester
{
    class Program
    {
        static void Main(string[] args)
        {
            mt19937.sgenrand(255);
            for(int i = 0; i < 10; i++)
                Console.WriteLine(mt19937.genrand());
        }
    }
}
mt19937.cs
using System;

public class mt19937
{
    /* Period parameters */
    private const int N = 312;
    private const int M = 156;
    private const ulong MATRIX_A = 0xB5026F5AA96619E9; /* constant vector a */
    private const ulong UPPER_MASK = 0xFFFFFFFF80000000; /* most significant w-r bits */
    private const ulong LOWER_MASK = 0x7FFFFFFF; /* least significant r bits */

    /* Tempering parameters */
    private const ulong TEMPERING_MASK_B = 0x9d2c5680;
    private const ulong TEMPERING_MASK_C = 0xefc60000;

    private static ulong TEMPERING_SHIFT_U(ulong y) { return (y >> 29); }
    private static ulong TEMPERING_SHIFT_S(ulong y) { return (y << 17); }
    private static ulong TEMPERING_SHIFT_T(ulong y) { return (y << 37); }
    private static ulong TEMPERING_SHIFT_L(ulong y) { return (y >> 43); }

    //static unsigned long mt[N]; /* the array for the state vector  */
    private static ulong[] mt = new ulong[N];

    // static int mti=N+1; /* mti==N+1 means mt[N] is not initialized */
    private static uint mti = N + 1; /* mti==N+1 means mt[N] is not initialized */

    /* initializing the array with a NONZERO seed */
    public static void sgenrand(ulong seed)
    {
        /* setting initial seeds to mt[N] using         */
        /* the generator Line 25 of Table 1 in          */
        /* [KNUTH 1981, The Art of Computer Programming */
        /*    Vol. 2 (2nd Ed.), pp102]                  */

        mt[0] = seed;
        for(mti = 1; mti < N; mti++) {
            mt[mti] = (6364136223846793005 * (mt[mti-1] ^ (mt[mti-1] >> 62)) + mti);
        }
    }

    private static ulong[/* 2 */] mag01 = { 0x0, MATRIX_A };
    /* generating reals */
    /* unsigned long */
    /* for integer generation */
    public static ulong genrand()
    {
        ulong y;

        /* mag01[x] = x * MATRIX_A  for x=0,1 */
        if(mti >= N) /* generate N words at one time */ {
            short kk;

            if(mti == N + 1) /* if sgenrand() has not been called, */ {
                sgenrand(5489); /* a default initial seed is used   */
            }

            for(kk = 0; kk < N - M; kk++) {
                y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
                mt[kk] = mt[kk + M] ^ (y >> 1) ^ mag01[y & 0x1];
            }

            for(; kk < N - 1; kk++) {
                y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
                mt[kk] = mt[kk + (M - N)] ^ (y >> 1) ^ mag01[y & 0x1];
            }

            y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
            mt[N - 1] = mt[M - 1] ^ (y >> 1) ^ mag01[y & 0x1];

            mti = 0;
        }

        y = mt[mti++];
        y ^= (y >> 29) & 0x5555555555555555;
        y ^= (y << 17) & 0x71D67FFFEDA60000;
        y ^= (y << 37) & 0xFFF7EEE000000000;
        y ^= (y >> 43);

        return y;
    }
}
For the rare C/C++ developer, here we go:
main.cpp
#include <iostream>
using namespace std;

extern "C" { // when using C, just include the file.
	#include "mt64.h"
}

int main(){
	init_genrand64(255);
	for(int i = 0; i < 10; i++)
		cout << genrand64_int64() << endl;
	return 0;
}
Header file, summary for user and for compiler (yes, we fluff our compiler that much)
mt64.h
/* initializes mt[NN] with a seed */
void init_genrand64(unsigned long long seed);

/* initialize by an array with array-length */
/* init_key is the array for initializing keys */
/* key_length is its length */
void init_by_array64(unsigned long long init_key[], 
		     unsigned long long key_length);

/* generates a random number on [0, 2^64-1]-interval */
unsigned long long genrand64_int64(void);


/* generates a random number on [0, 2^63-1]-interval */
long long genrand64_int63(void);

/* generates a random number on [0,1]-real-interval */
double genrand64_real1(void);

/* generates a random number on [0,1)-real-interval */
double genrand64_real2(void);

/* generates a random number on (0,1)-real-interval */
double genrand64_real3(void);
and finally: mt19937-64.c. Yes, I mix C and C++ in source code without fear, bitch.
#include <stdio.h>
#include "mt64.h"

#define NN 312
#define MM 156
#define MATRIX_A 0xB5026F5AA96619E9ULL
#define UM 0xFFFFFFFF80000000ULL /* Most significant 33 bits */
#define LM 0x7FFFFFFFULL /* Least significant 31 bits */


/* The array for the state vector */
static unsigned long long mt[NN]; 
/* mti==NN+1 means mt[NN] is not initialized */
static int mti=NN+1; 

/* initializes mt[NN] with a seed */
void init_genrand64(unsigned long long seed)
{
    mt[0] = seed;
    for (mti=1; mti<NN; mti++) 
        mt[mti] =  (6364136223846793005ULL * (mt[mti-1] ^ (mt[mti-1] >> 62)) + mti);
}

/* initialize by an array with array-length */
/* init_key is the array for initializing keys */
/* key_length is its length */
void init_by_array64(unsigned long long init_key[],
		     unsigned long long key_length)
{
    unsigned long long i, j, k;
    init_genrand64(19650218ULL);
    i=1; j=0;
    k = (NN>key_length ? NN : key_length);
    for (; k; k--) {
        mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 62)) * 3935559000370003845ULL))
          + init_key[j] + j; /* non linear */
        i++; j++;
        if (i>=NN) { mt[0] = mt[NN-1]; i=1; }
        if (j>=key_length) j=0;
    }
    for (k=NN-1; k; k--) {
        mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 62)) * 2862933555777941757ULL))
          - i; /* non linear */
        i++;
        if (i>=NN) { mt[0] = mt[NN-1]; i=1; }
    }

    mt[0] = 1ULL << 63; /* MSB is 1; assuring non-zero initial array */ 
}

/* generates a random number on [0, 2^64-1]-interval */
unsigned long long genrand64_int64(void)
{
    int i;
    unsigned long long x;
    static unsigned long long mag01[2]={0ULL, MATRIX_A};

    if (mti >= NN) { /* generate NN words at one time */

        /* if init_genrand64() has not been called, */
        /* a default initial seed is used     */
        if (mti == NN+1) 
            init_genrand64(5489ULL); 

        for (i=0;i<NN-MM;i++) {
            x = (mt[i]&UM)|(mt[i+1]&LM);
            mt[i] = mt[i+MM] ^ (x>>1) ^ mag01[(int)(x&1ULL)];
        }
        for (;i<NN-1;i++) {
            x = (mt[i]&UM)|(mt[i+1]&LM);
            mt[i] = mt[i+(MM-NN)] ^ (x>>1) ^ mag01[(int)(x&1ULL)];
        }
        x = (mt[NN-1]&UM)|(mt[0]&LM);
        mt[NN-1] = mt[MM-1] ^ (x>>1) ^ mag01[(int)(x&1ULL)];

        mti = 0;
    }
  
    x = mt[mti++];

    x ^= (x >> 29) & 0x5555555555555555ULL;
    x ^= (x << 17) & 0x71D67FFFEDA60000ULL;
    x ^= (x << 37) & 0xFFF7EEE000000000ULL;
    x ^= (x >> 43);

    return x;
}

/* generates a random number on [0, 2^63-1]-interval */
long long genrand64_int63(void)
{
    return (long long)(genrand64_int64() >> 1);
}

/* generates a random number on [0,1]-real-interval */
double genrand64_real1(void)
{
    return (genrand64_int64() >> 11) * (1.0/9007199254740991.0);
}

/* generates a random number on [0,1)-real-interval */
double genrand64_real2(void)
{
    return (genrand64_int64() >> 11) * (1.0/9007199254740992.0);
}

/* generates a random number on (0,1)-real-interval */
double genrand64_real3(void)
{
    return ((genrand64_int64() >> 12) + 0.5) * (1.0/4503599627370496.0);
}
No matter what you use, this output will signify your success.
3220586997909315655
3303451203970382242
11896436706893466529
8960318650144385956
4679212705770455613
15567843309247195414
6961994097256010468
10807484256991480663
11890420171946432686
15474158341220671739
So far I am taking the random number and masking it with 0xFFFF (though the output above is the raw 64bit numbers). 0xFFFF is even larger than the largest number returned by the C/C++ stdlib random function (0x7FFF) (which is pretty cute now that I compare).

Gladiators, begin!
......... Generated 888888 players in 782.2265 milliseconds

100 %
Split 888888 players into 2 444444 player teams in 7694.336 milliseconds.
In another scenario 8.9 million players take about 33 minutes and gets me a 50/50 split (I ran this in debug mode)

The only way to make my code get a result far from a 50/50 is to manually shift the balance by adding entries different from the rest. And obviously this can be experimented with usually only on small lists like for example a list of 10 players.
I am avoiding to put any more code here so if interested you can check it on GitHub
https://github.com/M-S-D/Team-Splitter
@MSD: What does your algo return when using genrand()%5000 with 100 values with a seed of say 100?
arithma wrote@MSD: What does your algo return when using genrand()%5000 with 100 values with a seed of say 100?
Generated 100 players in 2 milliseconds

100 %
Split 100 players into 2 50 player teams in 25 milliseconds.
50/50 split
To compare our 2 algos, we need the same input, I propose you generate a file containing the cases that have a bad performance on your algo and I would test them and compare results. You could upload it somewhere like mediafire or some online space.
That's why I ported the 64 bit generator to C#. For a given seed, it generates the exact same sequence of pseudo-random numbers.
So by sharing a seed (and any additional steps to shape the input to the algo), we can avoid having to upload random numbers to the internets.
I checked your code and you're still using the 32bit mersene twister.

random() % 5000 should be the formula you use to get each sequence number.
We'll make sure everything is in place tonight.