PHPGangsta - Der praktische PHP Blog

PHP Blog von PHPGangsta


Mein Spielplan-Algorithmus

with 12 comments

Vor 2 Wochen hatte ich ja dazu aufgerufen ein algorithmisches Problem zur Berechnung eines Spielplan zu lösen. Es gab in den Kommentaren einige gute Ansätze und auch eine gültige Lösung wenn ich es richtig gesehen habe, und wie versprochen werde ich heute meine Lösung veröffentlichen.

Vielleicht sollten wir uns nochmal das Grundproblem ins Gedächtnis rufen:

Wir haben folgende Ausgangslage: X Spieler möchten ein Turnier veranstalten, wobei jeweils einer gegen einen spielt (Duelle, deshalb sollte X gerade sein). Dabei soll jedoch niemand mehrfach gegen den selben Spieler antreten und es soll niemand ein Spielbrett zweimal benutzen dürfen. Es gibt X/2 Spielbretter, also auch für jeden Spieler X/2 Duelle.

Meine erste Lösung war recht schnell und auf den ersten Blick coole Lösung, ABER auch dieser Code hat das Problem dass es doppelte Paarungen gibt. Dieses Problem hatten fast alle Lösungen aus den Kommentaren auch.
Grundsätzlich funktioniert der Algorithmus wie folgt (bei 10 Spielern): Ich fülle am Anfang ein 5*5 Array, worin jede Zelle alle Spielernummern (0-9) enthält. Dann ziehe ich aus dem ersten Feld 2 zufällige Spieler, lösche alle anderen Einträge aus dieser Zelle und lösche diese beiden gezogenen Spieler auch aus der restlichen Zeile und Spalte. So stelle ich sicher dass ein Spieler nur einmal pro Runde und einmal auf jedem Spielfeld spielt. Das mache ich nun so lange bis ich eine Zelle finde wo es keine 2 Spieler mehr gibt, dann resette ich zum Anfangsarray ($startGrid) und beginne von vorn.

<?php
$player = 10;

$rounds = $player/2;
$startGrid = array();

$startTime = microtime(true);

for ($i=0; $i<$rounds; $i++) {
    for ($j=0; $j<$rounds; $j++) {
        $startGrid[$i][$j] = range(0, $player-1);
    }
}

while (true) {
    $grid = $startGrid;

    for ($j=0; $j<$rounds; $j++) {
        for ($i=0; $i<$rounds; $i++) {
            if (count($grid[$i][$j]) < 2) {
                continue 3;
            }

            $randomEntries = array_rand($grid[$i][$j], 2);

            $first = $grid[$i][$j][$randomEntries[0]];
            $second = $grid[$i][$j][$randomEntries[1]];

            $grid[$i][$j] = array($first => $first, $second => $second);

            for ($z=0; $z<$rounds; $z++) {
                if ($z != $i) {
                    unset($grid[$z][$j][$first]);
                    unset($grid[$z][$j][$second]);
                }
            }
            for ($z=0; $z<$rounds; $z++) {
                if ($z != $j) {
                    unset($grid[$i][$z][$first]);
                    unset($grid[$i][$z][$second]);
                }
            }
        }
    }

    outputPlan($grid);
    echo "\n".round((microtime(true)-$startTime), 2)." seconds\n";
    exit;
}

function outputPlan($grid) {
    global $rounds;

    for ($i=0; $i<$rounds; $i++) {
        for ($j=0; $j<$rounds; $j++) {
            echo str_pad(join('-', $grid[$i][$j]), 25);
        }
        echo "\n";
    }
}

Nachdem ich das Problem mit den doppelten Paarungen entdeckt hatte musste ich also nochmal überlegen und bin zu folgenden Code gekommen, der deutlich langsamer ist, aber (glaube ich) gültige Ergebnisse ausspuckt. Ich habe einen ähnlichen Ansatz wie beim ersten Versuch, speichere in jeder Zelle jedoch nicht alle Spieler, sondern alle Spielpaarungen.

<?php
$player = 10;

$rounds = $player/2;

$startTime = microtime(true);

$gameTable = array();
for ($i=0; $i<$player; $i++) {
    for ($j=$i+1; $j<$player; $j++) {
        $gameTable[] = array($i, $j);
    }
}

$startGrid = array();
for ($i=0; $i<$rounds; $i++) {
    for ($j=0; $j<$rounds; $j++) {
        $startGrid[$i][$j] = range(0, count($gameTable)-1);
    }
}

while (true) {
    $grid = $startGrid;

    for ($j=0; $j<$rounds; $j++) {
        for ($i=0; $i<$rounds; $i++) {
            if (count($grid[$i][$j]) == 0) {
            	echo "Abbruch in $i/$j\n";
                continue 3;
            }

            // Randomly pick one game
            $randomEntryIndex = array_rand($grid[$i][$j]);
            // remove all others in that cell
            $grid[$i][$j] = $randomEntryIndex;

            // remove all games from rest of row which have players in it we picked above
            for ($z=$i+1; $z<$rounds; $z++) {
                foreach ($grid[$z][$j] as $game) {
                	if (in_array($gameTable[$randomEntryIndex][0], $gameTable[$game]) ||
                		in_array($gameTable[$randomEntryIndex][1], $gameTable[$game])) {
                		unset($grid[$z][$j][$game]);
                	}
                }
            }

        	for ($z=$j+1; $z<$rounds; $z++) {
                foreach ($grid[$i][$z] as $game) {
                	if (in_array($gameTable[$randomEntryIndex][0], $gameTable[$game]) ||
                		in_array($gameTable[$randomEntryIndex][1], $gameTable[$game])) {
                		unset($grid[$i][$z][$game]);
                	}
                }
            }

            // remove all occurences of that exact match
            for ($k=0; $k<$rounds; $k++) {
        		for ($l=0; $l<$rounds; $l++) {
        			if (!($k==$i && $l==$j)) {
        				unset($grid[$k][$l][$randomEntryIndex]);
        			}
        		}
        	}

        }
    }

    outputPlan($grid);
    echo "\n".round((microtime(true)-$startTime), 2)." seconds\n";
    exit;
}

function outputPlan($grid) {
    global $rounds, $gameTable;

    for ($i=0; $i<$rounds; $i++) {
        for ($j=0; $j<$rounds; $j++) {
            echo str_pad(join('-', $gameTable[$grid[$i][$j]]), 25);
        }
        echo "\n";
    }
} 

Ja, ich weiß, nicht schön („global“ etc.), aber funktioniert, wenn auch langsamer als Fabians Lösung aus den Kommentaren des Aufruf-Artikels. Er sagte mir dass er mehrere Abende daran gesessen hat und die Lösung sein achter oder neunter Ansatz gewesen sei. Wirklich respektabel wie er sich da reingearbeitet und diese schöne Lösung erstellt hat.

Written by Michael Kliewe

August 5th, 2010 at 11:55 am

Posted in PHP

Tagged with , , ,

12 Responses to 'Mein Spielplan-Algorithmus'

Subscribe to comments with RSS or TrackBack to 'Mein Spielplan-Algorithmus'.

  1. Eine relativ einfache, wenn auch noch nicht implementierte Lösung hatte ich noch gefunden. Allerdiings hatte ich die noch nicht implementiert, da ich mit dem Weg noch etwas unzufrieden war:
    1) Finde 2 Primzahlen (möglichst nahe) Wurzel (x/2)
    2) Trage mit diesen Zahlen 1 und 1′ nach folgendem Muster ein
    2a) 1: pos(1)= 1; pos(2)=pos(1)+x/2+primzahl1
    1: pos(1)= 1; pos(2)=pos(1)+x/2+primzahl2
    Problem: Die beiden Zahlen treffen sich auf X/2/2, deshalb muss beim Durchlauf von 1′ einmal die Position mit der nächsten Zeile getauscht werden.
    3) Fülle die restlichen Felder auf.
    Dier Algo läuft rappelschnell, allerdings bin ich mit dieser Zeilentauschmogelei unzufrieden, aber da kommt noch was…

    Christoph

    5 Aug 10 at 12:09

  2. Was machst du, wenn es 11 Spieler gibt?

    Roman

    5 Aug 10 at 14:32

  3. Dann wird man für 12 Spieler berechnen und einer davon ist das Freilos.

    Michael Kliewe

    5 Aug 10 at 15:06

  4. Moin.

    Kannst du die Lösung für 12 Spieler angeben? Irgendwie kommt er bei mir zu keinem Ende… Ich glaube nämlich, dass es für diese Konstellation keine gültige Lösung gibt. Mehr dazu, wenn du meine Vermutung bestätigt hast. :-)

    – Andre

    Andre

    5 Aug 10 at 17:21

  5. Das nächste Mal sollte ich länger warten. :-)

    Andre

    5 Aug 10 at 18:46

  6. @Andre: Deshalb habe ich nicht geantwortet, das dauert, je nachdem wieviel Glück man hat, einige Minuten.
    Probier mal Fabians Lösung (und guck sie dir an), die ist deutlich schöner und schneller…

    Michael Kliewe

    5 Aug 10 at 19:05

  7. Mache ich einen Denkfehler oder ist das so einfach:

    $players=10;

    for ($j=0; $j<$players; $j++)
    {
    for ($i=$j+1; $i<$players; $i++)
    {
    echo $j." gegen ".$i."\n";
    }
    }

    Oder soll noch sortiert werden, wer gleichzeitig spielen kann?

    Dazu packt man das ganze in ein Array $p[$i][$j]=false und iteriert das ab und sucht dann z.B. jeweils die freien Spieler, setzt den Wert auf true, damit diese Kombination nicht nochmal spielt bis die Brettzahl erreicht ist, dann zurück auf Anfang, nächstes $p und gut.

    brummfondel

    19 Aug 10 at 15:08

  8. Wenn du jetzt noch die Duelle auf die Spielbretter verteilst ohne dass jemand ein Spielfeld doppelt benutzt geht es in die richtige Richtung. Aber ganz so einfach ist es dann doch nicht. Außerdem würde bei deinem Array, das sich die bereits stattgefundenen Duelle merkt, jedes Duell zwei mal vorkommen können: Das Duell „1 gegen 2“ ist das selbe wie „2 gegen 1“.

    Das schwierigste ist aber wohl die Duelle auf die Spielbretter zu verteilen ohne dass jemand doppelt auf einem Spielbrett spielt.

    Bin gespannt ob du weiterkommst, es ist wie gesagt recht kompliziert, bisher sind nur 2 funktionierende Lösungen hier im Blog aufgetaucht.

    Michael Kliewe

    19 Aug 10 at 15:52

  9. Moin.

    Ich glaube, ich habe heute eine effiziente Lösung (O(n²) Zeitkomplexität und O(1) Platzkomplexität) gefunden. Es sind ca. 50 Zeilen Haskell-Code. Falls noch Interesse an einem solchen Algorithmus bestehen sollte, kannst du mir ja eine E-Mail schreiben. :-)

    – Andre

    Andre

    24 Nov 10 at 17:34

  10. Moin.

    Ich habe die Lösung soeben auf PHP portiert, siehe http://pastie.org/1329676. Sollte jemand Fehler entdecken, würde ich mich freuen, wenn ihr mich darauf aufmerksam machen würdet. Ansonsten habe ich vor, in Kürze meine Lösung zu erläutern.

    – Andre

    Andre

    28 Nov 10 at 12:04

  11. @Andre: Habe dein Script ein paar mal durchlaufen lassen und ich finde keine Fehler, und es ist super schnell, Hammer.

    Ein paar kleine Unschönheiten am Code wären zu bemängeln, aber sonst eine schöne Lösung, die ich auch noch nicht ganz verstehe muss ich zugeben. Es sieht irgendwie nach einer Rotation aus, die aber nicht ganz regelmäßig zu sein scheint. Du wirst uns da sicherlich aufklären 😉

    Die zwei Unschönheiten schnell aufgelistet:
    – die module() Funktion kannst du dir sparen, es gibt den % Operator
    http://php.net/manual/de/language.operators.arithmetic.php
    (wenn ich die Funktion hätte schreiben müssen wäre übrigens was anderes dabei herausgekommen, deine modulo-Funktion dürfte bei großen Zahlen recht langsam sein)
    – das echo in der letzten Zeile kann weg, plan() hat keinen Rückgabewert

    Bin beeindruckt!

    Michael Kliewe

    28 Nov 10 at 12:28

  12. Die „modulo“-Funktion habe ich geschrieben, da der %-Operator ein anderes Verhalten hat, als ich es von der Modulo-Funktion erwartet habe. „-3 % 2“ müsste meiner Erwartung nach „1“ zurückgeben, gibt aber „-1“ zurück.
    Mit deiner Einschätzung bzgl. der Geschwindigkeit hast du natürlich Recht. Wahrscheinlich wäre ich mit folgender Definition besser gefahren:
    $r = $k % $n;
    return ($r < 0 ? $r+$n : $r);

    Danke für dein Lob. :-) Wenn man eine gerade Anzahl von Paaren (bzw. Tischen bzw. Runden) hat, ist die Lösung einfach und wurde, glaube ich, bereits mehrfach genannt. Bei gerader Anzahl von Paaren funktioniert diese Lösung jedoch nicht. Nach ein bisschen rumprobieren habe ich eine Möglichkeit entdeckt, wie man aus einer Lösung mit n (ungerade) Paaren in eine Lösung für (n-1) Paare erzeugen kann – und das steht im Algorithmus. Warum es funktioniert… Das werde ich dann in meinem Artikel (wahrscheinlich Dienstag) beschreiben. :-)

    Andre

    28 Nov 10 at 12:54

Leave a Reply

You can add images to your comment by clicking here.