• Coding

  • Exercise - Team Balancing

@MSD: This 98minutes could be just a lucky guess with the algorithm. I do not think our combination technique could really hold against the huge combinatorial explosion we're dealing with.

So here's a challenge now:
Balance teams from a pool of ranks growing from 0 to 999 inclusive.
I got the difference down to 2. PS: No, I have not asked google for an answer yet. Computation time [wrong]~10 seconds[/wrong][correct]instantaneous[/correct].
I can not pledge that it is optimal however.
-Note, again: This solution is definitely not optimal since if you split the array in half, and take every other element from each array, and then join them, they'll return a difference of zero (always for any sequential array). This means we need another method to evaluate heuristic algorithms. Am satisfied enough with this algo, though I wish I could find some academic material for such a problem.
diff = 2
on the left
6 8 10 11 12 13 14 15 17 18 19 20 21 22 23 24 26 27 28 29 30 32 33 34 35 36 37 38 39 40 42 43 45 47 50 57 58 60 65 67 69 70 74 75 77 78 79 81 86 87 89 90 93 97 102 105 106 107 108 110 111 112 116 119 123 125 126 127 130 133 135 136 137 139 140 141 142 143 145 147 148 149 152 154 158 161 162 164 165 167 169 170 171 173 175 176 177 180 182 183 184 188 189 192 194 195 196 200 201 203 204 205 206 207 209 210 211 214 216 217 218 219 221 226 228 229 231 234 239 242 243 247 248 251 252 253 254 255 262 263 265 266 267 268 270 271 273 277 279 280 282 284 290 293 295 298 300 303 304 312 314 315 316 317 318 320 322 325 326 335 336 339 341 343 345 346 348 349 351 352 353 354 357 358 359 360 363 366 367 368 374 376 377 379 380 381 383 384 385 390 391 396 397 403 405 406 408 411 413 415 417 420 422 425 426 427 429 433 434 438 440 442 445 447 448 449 451 459 460 461 465 467 468 469 472 473 475 479 484 485 487 491 492 493 495 497 500 501 503 506 512 514 515 518 519 523 529 535 536 537 538 539 540 544 549 551 552 553 554 555 556 557 559 562 565 568 570 571 576 577 578 579 582 586 592 593 594 595 601 602 603 605 609 610 614 617 618 622 623 624 626 629 630 632 633 634 635 638 642 643 644 646 647 649 651 656 657 659 661 663 664 666 668 671 675 677 678 679 682 683 685 686 687 692 693 694 699 700 704 705 706 707 708 710 712 713 714 715 716 717 718 719 721 722 723 724 725 726 728 729 730 731 732 734 735 736 737 739 742 744 745 746 748 750 753 754 756 759 760 761 762 763 767 769 771 772 774 775 776 777 778 781 782 784 788 790 792 793 794 795 796 797 800 807 810 813 814 816 817 818 820 821 823 824 825 831 833 834 835 836 837 838 839 840 842 844 845 847 849 854 855 856 858 859 861 862 863 865 866 870 871 872 874 880 881 888 892 893 896 897 900 902 905 906 907 908 909 910 912 913 915 920 921 925 927 931 934 935 938 941 944 945 946 949 951 953 954 956 959 961 966 971 972 974 976 977 978 979 980 981 984 986 988 989 992 993 994 997 998 999 
-----------
on the right
0 1 2 3 4 5 7 9 16 25 31 41 44 46 48 49 51 52 53 54 55 56 59 61 62 63 64 66 68 71 72 73 76 80 82 83 84 85 88 91 92 94 95 96 98 99 100 101 103 104 109 113 114 115 117 118 120 121 122 124 128 129 131 132 134 138 144 146 150 151 153 155 156 157 159 160 163 166 168 172 174 178 179 181 185 186 187 190 191 193 197 198 199 202 208 212 213 215 220 222 223 224 225 227 230 232 233 235 236 237 238 240 241 244 245 246 249 250 256 257 258 259 260 261 264 269 272 274 275 276 278 281 283 285 286 287 288 289 291 292 294 296 297 299 301 302 305 306 307 308 309 310 311 313 319 321 323 324 327 328 329 330 331 332 333 334 337 338 340 342 344 347 350 355 356 361 362 364 365 369 370 371 372 373 375 378 382 386 387 388 389 392 393 394 395 398 399 400 401 402 404 407 409 410 412 414 416 418 419 421 423 424 428 430 431 432 435 436 437 439 441 443 444 446 450 452 453 454 455 456 457 458 462 463 464 466 470 471 474 476 477 478 480 481 482 483 486 488 489 490 494 496 498 499 502 504 505 507 508 509 510 511 513 516 517 520 521 522 524 525 526 527 528 530 531 532 533 534 541 542 543 545 546 547 548 550 558 560 561 563 564 566 567 569 572 573 574 575 580 581 583 584 585 587 588 589 590 591 596 597 598 599 600 604 606 607 608 611 612 613 615 616 619 620 621 625 627 628 631 636 637 639 640 641 645 648 650 652 653 654 655 658 660 662 665 667 669 670 672 673 674 676 680 681 684 688 689 690 691 695 696 697 698 701 702 703 709 711 720 727 733 738 740 741 743 747 749 751 752 755 757 758 764 765 766 768 770 773 779 780 783 785 786 787 789 791 798 799 801 802 803 804 805 806 808 809 811 812 815 819 822 826 827 828 829 830 832 841 843 846 848 850 851 852 853 857 860 864 867 868 869 873 875 876 877 878 879 882 883 884 885 886 887 889 890 891 894 895 898 899 901 903 904 911 914 916 917 918 919 922 923 924 926 928 929 930 932 933 936 937 939 940 942 943 947 948 950 952 955 957 958 960 962 963 964 965 967 968 969 970 973 975 982 983 985 987 990 991 995 996
Here is my final solution, and I think this is the one, it works on big numbers of players in a very fast time, I really enjoyed this one ;) 
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 void Split(Player[] team1, Player[] team2)
        {
            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 = 1000;
            _Players = new Player[_TotalPlayers];
            for (int i = 0; i < _TotalPlayers; i++)
                _Players[i] = new Player { Name = i.ToString(), Rating = i };
            InsureTotalPlayers(args);
            GeneratePlayers();
            SplitAndReportToFile();
            Console.Write("Press any key to exit.");
            Console.Read();
        }
    }
}
You can generate players randomly or have them preset like in the above code ( I used arithma's suggestion and got a clear cut split 50/50).
Generated 1000 players in 0 milliseconds
Split 1000 players into 2 500 player teams in 41.9922 milliseconds.
[Edit]Modified to avoid overflow (need to test for more extreme cases).[/Edit]
And here's mine.
I just tried it with 10,000 random values (between 0 and 0x7fff), it returns on the spot.

@MSD: I just tried your code with 10,000, but I think there's an overflow with currentDiff * diff > 0. I replaced it with 
if((currentDiff > 0) == (diff > 0))
Still the algorithm doesn't return. I would really appreciate it if you'd look at it for a bit, as I am comparing something in the algo's, and seeing if a particular thing I did spared me quadratic growth or not. 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;

struct Solver{
	vector<int> left;
	vector<int> right;
	int lsum;
	int rsum;

	Solver(vector<int> & v){
		left.insert(left.begin(), v.begin(), v.begin() + v.size()/2);
		right.insert(right.begin(), v.begin() + v.size()/2, v.end());
		sort(left.begin(), left.end());
		sort(right.begin(), right.end());

		lsum = 0;
		rsum = 0;
		for(int i = 0; i < left.size(); i++)
			lsum += left[i];
		for(int i = 0; i < right.size(); i++)
			rsum += right[i];

		if(lsum > rsum){
			swap(left, right);
			swap(lsum, rsum);
		}

		while(step());
	}

	bool step(){
		int diff = rsum - lsum;
		for(auto curr = right.rbegin(); curr != right.rend(); curr++){
			auto found = lower_bound(left.begin(), left.end(), *curr - diff/2);
			if(found != left.end() && (diff + 2 * *found - 2 * *curr > 0) && (*found - *curr < 0)){
				lsum += + *curr - *found;
				rsum += - *curr + *found;
				diff = rsum - lsum;
				swap(*found, *curr);
				sort(left.begin(), left.end());
				sort(right.begin(), right.end());
				return true;
			}
		}
		return false;
	}
};

int main(){
	vector<int> v;
	int const K = 10000;
	for(int i = 0; i < K; i++){
		v.push_back(rand());
	}
	vector<int> shuffled(K);
	for(int i = 0; i < K; i++){
		int index = rand()%v.size();
		shuffled[i] = v[index];
		v.erase(v.begin()+index);
	}

	Solver s(shuffled);
	cout << "diff = " << s.rsum - s.lsum << endl;
	cout << "on the left\n";
	for_each(s.left.begin(), s.left.end(), [](int x){ cout << x << " ";});
	cout << endl;
	cout << "-----------\n";
	cout << "on the right\n";
	for_each(s.right.begin(), s.right.end(), [](int x){ cout << x << " ";});
	cout << endl;

	return 0;
}
arithma wroteAnd here's mine.
@MSD: I just tried your code with 10,000, but I think there's an overflow with currentDiff * diff > 0.
@arithma: please check if it solves your problem now
- Sort the 10 players according to their rating: p1 p2 p3 ... p10:

Team1 = p1 p10, p3 p8, p5
Team2 = p2 p9, p4 p7, p6

Observe how I chose the indices of each team.
the_pessimist wrote- Sort the 10 players according to their rating: p1 p2 p3 ... p10:

Team1 = p1 p10, p3 p8, p5
Team2 = p2 p9, p4 p7, p6

Observe how I chose the indices of each team.
I that a solution or a question?
I put the code neck to neck on my machine, compiled both in Release mode, both taking in arrays ranging from 1 to 10,000.
My program solves it with the following output: 
shuffled
1000 steps done
1000 steps done
1000 steps done
1000 steps done
1000 steps done
1000 steps done
1000 steps done
1000 steps done
1000 steps done
2499975000 - 2499975000 = 0
It does so in less than a minute.
It also got rid of those annoying "2" differences from the output.

Both programs have been changed to use 64-bit integers.
I am sorry MSD, but your program has yet to return :P

To change MSD's code, just replace int with long to handle those pesky large 100,000 values.

64-bit, arithma's code. 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;

struct Solver{
	vector<_int64> left;
	vector<_int64> right;
	_int64 lsum;
	_int64 rsum;

	Solver(vector<_int64> & v){
		left.insert(left.begin(), v.begin(), v.begin() + v.size()/2);
		right.insert(right.begin(), v.begin() + v.size()/2, v.end());
		sort(left.begin(), left.end());
		sort(right.begin(), right.end());

		lsum = 0;
		rsum = 0;
		for(_int64 i = 0; i < left.size(); i++)
			lsum += left[i];
		for(_int64 i = 0; i < right.size(); i++)
			rsum += right[i];

		if(lsum > rsum){
			swap(left, right);
			swap(lsum, rsum);
		}

		int steps = 0;
		while(step()){
			steps++;
			if(steps%1000==0)
				cout << "1000 steps done" << endl;
			
		}
		cout << rsum << " - " << lsum << " = " << rsum - lsum << endl;
	}

	bool step(){
		_int64 diff = rsum - lsum;
		for(auto curr = right.rbegin(); curr != right.rend(); curr++){
			auto found = lower_bound(left.begin(), left.end(), *curr - diff/2);
			//if(found != left.end() && (diff + 2 * *found - 2 * *curr < diff) && (*found - *curr < 0)){
			if(found != left.end() && (abs(diff + 2 * *found - 2 * *curr) < diff)){
				lsum += + *curr - *found;
				rsum += - *curr + *found;
				diff = rsum - lsum;
				swap(*found, *curr);
				sort(left.begin(), left.end());
				sort(right.begin(), right.end());

				if(lsum > rsum){
					swap(left, right);
					swap(lsum, rsum);
				}
				return true;
			}
		}
		return false;
	}

	void randomswaps(_int64 n){
		for(_int64 i = 0; i < n; i++){
			_int64 l = rand()%left.size();
			_int64 r = rand()%right.size();
			lsum += right[r] - left[l];
			rsum += left[l] - right[r];
			swap(left[l], right[r]);
		}
		if(lsum > rsum){
			swap(left, right);
			swap(lsum, rsum);
		}
	}
};

int main(){
	vector<_int64> v;
	_int64 const K = 100000;
	for(_int64 i = 0; i < K; i++){
		v.push_back(i);//rand());
	}
	vector<_int64> shuffled(K);
	for(_int64 i = 0; i < K; i++){
		_int64 index = rand()%v.size();
		shuffled[i] = v[index];
		v.erase(v.begin()+index);
	}
	cout << "shuffled" << endl;

	Solver s(shuffled);
	return 0;
	cout << "diff = " << s.rsum - s.lsum << endl;
	cout << "on the left\n";
	for_each(s.left.begin(), s.left.end(), [](_int64 x){ cout << x << " ";});
	cout << endl;
	cout << "-----------\n";
	cout << "on the right\n";
	for_each(s.right.begin(), s.right.end(), [](_int64 x){ cout << x << " ";});
	cout << endl;

	return 0;
}
@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?