Algorithmus für faire teams?

[Listing]

Hi C++-Board-User

Ich habe die ehrenvolle Aufgabe erhalten, für ein
online Spiel, in dem wir (ich und eine kleine Gruppe von Leuten) ein Turnier machen wollen (Es wird sowohl 1 vs 1 vs 1, wie auch 1 vs 1 unterstützt).
Die Spielerzuteilung zu übernehmen.

Hier eine von mir erstellte Skizze:
http://img3.imagebanana.com/img/xb3wd58r/competition.jpg

Zwei Grundsätze:
A) Wir möchten nicht, dass Spieler mit dem gleichen Clan (Gruppe, die sich zusammen anmeldet) und der gleichen Nationalität am Anfang direkt gegeneinander kämpfen müssen, das stärkt den Teamgeist.
Es soll nur die ursprüngliche Zusammenstellung (Stage 1) berücksicht werden, es ist nicht schlimm, wenn sich starke und schwache Gegner in der zweiten Runde treffen (da es ohnehin nur 3 Stages gibt).
C) Wir verfügen über Aufzeichnungen der Spielstärke der jeweiligen Gegner. (einmal die Siegesrate in Prozent, und die gewonnen Spiele). Wir haben uns schon überlegt hierraus einen "Skill" (Spielstärke) zu berechnen. Das wäre dann z.B. eine Zahl zwischen 1 und 1000. Wir möchten die Kombination dann so, dass die Spielstärke der 3 Gegner ausgeglichen (möglichst nah bei einander) ist.

Eine beispielhafte Spielerliste (Wir schätzen mit an die 90 Spieler):
[No][LNG][CLAN][NAME][SPIELSTAERKE]
[1] [DE] [MTW] [Dedalus] [314]
[2] [DE] [MTW] [SPQR Roma Victori] [512]
...
[40] [FR] [MUZ] [Mr.Potato-Head#71] [941]

Ich hab das schon Greedy gemacht, das heißt, es wird von allen Kombinationen, einen Spieler mit zwei anderen zu kombinieren, die am besten zu einander passen. Leider bleiben dann am Ende oft welche mit der gleichen Nationalität oder Clan über und es ist ich glaube nicht optimal und ineffizient.

Kann man sowas überhaupt lösen? Und wenn ja wäre ich über Ansätze gespannt.

Vielen Dank
Listing

[vlad_tepesch]

und C) sind aber schon irgendwioe ungerecht.

weil da schwache weiterkommen und starke direkt am anfang aussteigen.

Das heißt in erster runde gibt es eventuell spannende kämpfe, da gleichstarke gegeneinenaer kämpfen.
Im Halbfinale steht dann der Sieger aus der schwachen gruppe gegen den sieger aus der starken gruppe, was ein recht langweiliges match geben sollte.

Ich würde entweder eine total zufällige Auswahl treffen, oder in die vorrunde jeweils die skills mixen.