[PHP] Algorithmus gesucht für Spielplan

martin · 1 Juni 2011

Hallo

mit einem kleinen php Skript lasse ich mir momentan für ein Kleinfeldturnier die Paarungen zusammenstellen. Jeder spielt gegen jeden und es werden dann dementsprechende Arrays erzeugt:
$game[0]['home'] = 1;
$game[0]['visitor'] = 2;
$game[1]['home'] = 3;
$game[1]['visitor'] = 4;
usw.
das klappt auch wunderbar. Im Array $game habe ich nun alles so wie ich es haben möchte, mit einem kleinen Schönheitsfehler. Und zwar möchte ich, dass vermieden wird, dass eine Mannschaft zwei Spiele unmittelbar hintereinander hat. Ok ich weiß, dass das nicht immer möglich ist, aber je mehr Mannschaften sind, desto besser sollte es sich ausgehen. Also ich suche nach einem Algor. der mir das "so gut es halt geht" macht. Meine Ansätze mit Arrays tauschen in einer while schleife schlugen alle fehl.
Ich bräuchte auch nicht unbedingt das fertige Skript, wenn mir jemand in Worten sagen kann wie ich das am besten anstelle, wäre super für mich.

Danke

lockdoc · 1 Juni 2011

du koenntest ja beispielsweise in dem team array (falls es einen gibt) einen index pflegen.
Beim start stehen alle auf Null, haben 2 Teams miteinander gespielt, werden deren (und alle nicht auf 0 stehenden indexe um 1 inkrementiert).

Die schleife, die fuer die gameverteilung zustaendig ist, sucht 2 teams mit dem index 0, oder jeweils den niedrigsten werten, die gefunden werden. So muesste es eigentlich immer gut verteilt sein

Edit:
Ne oben ist ein Denkfehler!

+ Also Indexe fangen bei 0 an
+ Spielen 2 Teams werden deren Indexe auf 1 gesetzt und alle anderen, die nicht 0 sind werden inkrementiert
+ Zuerst muessen alle 0er indexe spielen und danach immer die hoechsten (welche nach dem Spielen wieder auf 1 gesetzt werden)

oenone · 1 Juni 2011

Hier gibt es einen schönen Algorithmus zur Turnier-Planung: http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo36.php

martin · 1 Juni 2011

@lockdoc
danke, so ganz steige ich da noch nicht durch, aber i mach jetzt mal ein paar tests

@oneone
den Link habe ich bei meiner Google-Recherche auch schon gefunden, das Problem dabei ist, dass die Spiele in Spieltage aufgeteilt werden und an einem Spieltag niemand doppelt spielt. Ich aber habe alle Spiele am selben Tag und möchte, dass es so selten als möglich vorkommt, dass eine Mannschaft 2 Spiele hintereinander machen muss. Trotzdem danke für deine Mühen

nakal · 1 Juni 2011

Klappt das mit einer Backtracking-Implementation? Sprich: so lange rekursiv das übriggebliebene nichtkollidierende Spiel reinpacken bis alles eine Lösung gefunden ist.

lockdoc · 1 Juni 2011

Also nochmal kurz zur Erklaerung. Ich habe auch noch ein Detail vergessen. Du musst noch irgendwo abspeichern, wer schon gegen wen gespielt hat

Du hast einen Team Array, wo die teams drinne sind

Code:

$team[$i]

Dieser hat ein zusaetzliches feld

Code:

$team[$i]['battle_index']

Dann brauchst du noch irgendwas wo du abspeicherst, wer schon gegen wen gespielt hat.

Vorraussetzung:
+ Zuerst ist bei allen eintraegen der 'battle_index' auf null gesetzt.

Lauf-1
+ Du suchst dir per schleife 2 teams raus, bei denen der index auf null ist
+ Die laesst du gegeneinander antreten
+ Danach wird deren Index auf 1 gesetzt (um 1 inkrementiert)

Lauf-2
+ Du suchst dir wieder 2 teams mit dem battle_index==0 raus
+ Die Spielen
+ Deren Index wird danach auf 1 gesetzt
+ zusaetzlich werden alle battle_index>0 (also die vom Lauf-1) um 1 inkrementiert

Lauf-X
Annahme: Es gibt keine Teams mehr mit dem battle_index==0, d.h. alle haben 1x gespielt
+ Du ordnest dir den array absteigend nach dem battle_index (groeste zuerst)
+ Nimmst dir den ersten (groessten), danach gehst du absteigend in dem array durch und vergleichst mit dem naechst niedrigem Wert, ob dir schon gegeneinander gespielt haben. Wenn ja, gehst du weiter im Array, wenn nein, dann nimmst du den.
+ Nach dem Spielen, werden die beiden Teams wieder auf 1 gesetzt

Das sollte eigentlich die groestmoegliche Spanne zwischen den Spieltagen pro Team schaffen. Hmm, eventuell ist das auch viel zu kompliziert umgesetzt...

oenone · 1 Juni 2011

martin schrieb:
@oneone
den Link habe ich bei meiner Google-Recherche auch schon gefunden, das Problem dabei ist, dass die Spiele in Spieltage aufgeteilt werden und an einem Spieltag niemand doppelt spielt. Ich aber habe alle Spiele am selben Tag und möchte, dass es so selten als möglich vorkommt, dass eine Mannschaft 2 Spiele hintereinander machen muss. Trotzdem danke für deine Mühen

Das mit den Spieltagen ist doch irrelevant? Stell dir das als "Runden" vor.

Erste Runde/Tag: Alle spielen einmal.
Dann merkst du dir, welche beiden als letztes gespielt hatten.
Zweite Runde/Tag: Such das Pairing raus, das keine der beiden gemerkten enthält. Die restlichen Pairings der Runde/des Tags können danach ohne Überprüfung spielen.
Wieder letzte beiden Teams merken
Dritte Runde: Selbes wie vorher.
etc...

martin · 2 Juni 2011

Danke für eure Vorschläge. Ich werde mich jetzt mal an den Tip von oneone machen und das Ganze ausprobieren.
@lockdoc danke für die ausführliche Beschreibung, du hast es geschafft, damit wurde mir Einiges klarer und ich glaube die Sache jetzt viel besser verstanden zu haben

martin · 3 Juni 2011

Ich komm immer noch nicht weiter

Moin

gestern war ich stundenlang am basteln, aber ich bekomme es einfach nicht hin. Folgenden Funktion habe ich zum Erstellen der Spieltage:

PHP:

function generateRoundRobinPairings($num_teams, $first_team='first', $second_team='second') {
    // Do we have a positive number of players? If not, default to 4.
    $num_teams = ($num_teams > 0) ? (int)$num_teams : 4;
    // If necessary, round up number of players to nearest even number.
    $num_teams += $num_teams % 2;

    // Format for pretty alignment of pairings across rounds.
    $format = "%0" . ceil(log10($num_teams)) . "d";
    $pairing = "$format-$format ";

    $games = array();

    // Generate the pairings for each round.
    for ($round = 1; $round < $num_teams; $round++) {
        $players_done = array();
        // Pair each player except the last.
        for ($player = 1; $player < $num_teams; $player++) {
            if (!in_array($player, $players_done)) {
                // Select opponent.
                $opponent = $round - $player;
                $opponent += ($opponent < 0) ? $num_teams : 1;
                // Ensure opponent is not the current player.
                if ($opponent != $player) {
                    // Choose colours.
                    if (($player + $opponent) % 2 == 0 xor $player < $opponent) {
                        // Player plays white.
                      $games[$round][$player][$first_team] = $player;
                      $games[$round][$player][$second_team] = $opponent;

                    }else{
                        // Player plays black.
                      $games[$round][$player][$first_team] = $opponent;
                      $games[$round][$player][$second_team] = $player;
                    }

                    // This pair of players are done for this round.
                    $players_done[] = $player;
                    $players_done[] = $opponent;
                }
            }
        }

        // Pair the last player.
        if ($round % 2 == 0) {
          $opponent = ($round + $num_teams) / 2;
          // Last player plays white.
          $games[$round][$player][$first_team] = $num_teams;
          $games[$round][$player][$second_team] = $opponent;
        } else {
          $opponent = ($round + 1) / 2;
          // Last player plays black.
          $games[$round][$player][$first_team] = $opponent;
          $games[$round][$player][$second_team] = $num_teams;
        }
    }
    return $games;
}

Das klappt auch wunderbar, nur schaffe ich es nicht, bei ungerader Anzahl die entsprechenden Spiele zu entfernen und auch nicht, die die zweimal hintereinander spielen, auszutauschen mit dem nächsten Spiel, so wie von oneone vorgeschlagen.
Hier mal der letzte meiner Versuche:

PHP:

$games = generateRoundRobinPairings(5);


foreach ($games as $r_key => $r_value){
    $change = false;
    echo "Round:".$r_key."<br>";
    foreach ($r_value as $rr_key => $rr_value){
        
        if (isset($lasth) && isset($lastv)){
            if ($lasth==$rr_value['first'] OR $lasth==$rr_value['second'] OR $lastv==$rr_value['first'] OR $lastv==$rr_value['second']){
                //$change = true;
                echo "change".$r_value[$lastk]['first']."-".$r_value[$lastk]['second']."->".$r_value[$rr_key]['first']."-".$r_value[$rr_key]['second'];
                $tmp = $r_value[$lastk];
                $r_value[$lastk] = $r_value[$rr_key];
                $r_value[$rr_key] = $tmp;
                break;
            }
        }

        //}
        $lastk=$rr_key;
        $lasth=$rr_value['first'];
        $lastv=$rr_value['second'];

        echo "".$lastk."->".$lasth."-".$lastv."<br>";
    }
    echo "<br>";

}

ich weiß, warum es nicht funktioniert, nämlich weil die keys immer die playerids sind und nicht wie von mir erwartet von 0 hochgezählt werden. Leider aber habe ich keinen Plan, wie ich das oben Gewünschte anstellen soll.

Bitte gebt mir einen Tip, ich steh'aufm Schlauch. :grumble:

Danke

lockdoc · 3 Juni 2011

Also ich hab mal auf die schnelle was gebastelt.
Weiss allerdings nicht ob es funktioniert, da ich es nur trocken in den Editor geschrieben habe. (Hab grad nix zum interpretieren zur Hand).

PHP:

<?php
// maximum possible number of games
function getMaxGames($how_many_teams)
{
	$rounds	= 0;

	while ($how_many_teams-1)
	{
		$rounds += $how_many_teams;
		$how_many_teams--;
	}
	return ($rounds);
}

// note: teams is by reference!
// resets it to '1'
function resetBattleIndex($id, &$teams)
{
	for ($i=0; $i<sizeof($teams); $i++)
	{
		if ( $team[$i]['id'] $id )
		{
			$team[$i]['battle_index'] = 1;
			return (1);
		}
	}
}

// $games[$i]['team1_id']
// $games[$i]['team2_id']
// check if teams have already played agains each other
function alreadyPlayed($id1, $id2, $games)
{
	if !(sizeof($games))
		return (0);

	for ($i=0; $i<sizeof($games)； $i++)
		if ( ($games[$i]['team1_id'] == $id1 && $games[$i]['team2_id'] == $id2) ||
			 ($games[$i]['team1_id'] == $id2 && $games[$i]['team2_id'] == $id1) )
			return (1);
}

// returns next team id or 0 if all teams have played
function getNotPlayedTeamId($teams, $except_id = 0)
{
	for ($i=0; $i<sizeof($teams)； $i++)
		if ( !$team[$i]['battle_index'] &&  $team[$i]['id'] != $except_id )
			return ($team[$i]['id']);

	return (0); 
}

// returns the team id of the team with the highest battle index
function getPlayedTeamId($teams, $except_id = 0)
{
	$offset = 0;
	$id		= 0;

	for ($i=0; $i<sizeof($teams); $i++)
	{
		if ( $team[$i]['battle_index'] > $offset && $team[$i]['id'] != $except_id )
		{
			$id		= $team[$i]['id'];
			$offset	= $team[$i]['battle_index'];
		}
	}
	return ($id);
}



$num_of_teams		= sizeof($teams);
$max_games			= getMaxGames($num_of_teams);
$game_count			= 0;


for ($i=0; $i<$max_games; $i++)
{
	$team1_id = getNotPlayedTeamId($teams);
	$team1_id = ( !$team1_id ? getNextTeamId($teams) : );

	$team2_id = getNotPlayedTeamId($teams, $team1_id);
	$team2_id = ( !$team2_id ) ? getNextTeamId($teams, $team1_id) : );

	// this is the dirty trick:
	// reset team2 battle index to '1'
	// decrement $i by 1, so this run did not exist
	// redo the run, now team2, should be a different one
	if ( alreadyPlayed($team1_id, $team2_id, $games) )
	{
		resetBattleIndex($team2_id, $teams);
		$i--;
	}
	else
	{
		$games[$game_count]['team1_id'] = $team1_id;
		$games[$game_count]['team2_id'] = $team2_id;
		resetBattleIndex($team1_id, $teams);
		resetBattleIndex($team2_id, $teams);
		$game_count++;
	}
}
?>

Ist auch erstmal sehr unperformant, da in der main loop, immer nach noch nich gespielten teams gekuckt wird, man koennte irgendwo ne flag setzen, wenn man weiss dass alle schonmal 1x gespielt haben.

martin · 3 Juni 2011

hallo lockdoc

danke für die Mühe, die du dir machst. Ein paar Kleinigkeiten habe ich an der Syntax ausgebessert, hier poste ich mal meine akutelle Version, die mir leider in eine Endlosschleife springt, ohne Fehlermeldungen.

PHP:

<?php
// maximum possible number of games
function getMaxGames($how_many_teams)
{
    $rounds    = 0;

    while ($how_many_teams-1)
    {
        $rounds += $how_many_teams;
        $how_many_teams--;
    }
    return ($rounds);
}

// note: teams is by reference!
// resets it to '1'
function resetBattleIndex($id, &$teams)
{
    for ($i=0; $i<sizeof($teams); $i++)
    {
        if ( $teams[$i]['id']==$id )
        {
            $teams[$i]['battle_index'] = 1;
            return (1);
        }
    }
}

// $games[$i]['team1_id']
// $games[$i]['team2_id']
// check if teams have already played agains each other
function alreadyPlayed($id1, $id2, $games)
{
    if (!sizeof($games))
        return (0);

    for ($i=0; $i<sizeof($games); $i++)
        if ( ($games[$i]['team1_id'] == $id1 && $games[$i]['team2_id'] == $id2) ||
             ($games[$i]['team1_id'] == $id2 && $games[$i]['team2_id'] == $id1) )
            return (1);
}

// returns next team id or 0 if all teams have played
function getNotPlayedTeamId($teams, $except_id = 0)
{
    for ($i=0; $i<sizeof($teams); $i++)
        if ( !$teams[$i]['battle_index'] &&  $teams[$i]['id'] != $except_id )
            return ($teams[$i]['id']);

    return (0);
}

// returns the team id of the team with the highest battle index
function getPlayedTeamId($teams, $except_id = 0)
{
    $offset = 0;
    $id        = 0;

    for ($i=0; $i<sizeof($teams); $i++)
    {
        if ( $teams[$i]['battle_index'] > $offset && $teams[$i]['id'] != $except_id )
        {
            $id        = $teams[$i]['id'];
            $offset    = $teams[$i]['battle_index'];
        }
    }
    return ($id);
}


$team[0]['battle_index'] = 0;
$team[0]['id'] = 0;
$team[1]['battle_index'] = 0;
$team[1]['id'] = 1;
$team[2]['battle_index'] = 0;
$team[2]['id'] = 2;
$team[3]['battle_index'] = 0;
$team[3]['id'] = 3;
$team[4]['battle_index'] = 0;
$team[4]['id'] = 4;

$num_of_teams        = sizeof($teams);
$max_games            = getMaxGames($num_of_teams);
$game_count            = 0;


for ($i=0; $i<$max_games; $i++)
{
    $team1_id = getNotPlayedTeamId($teams);
    $team1_id = ( !$team1_id ? getPlayedTeamId($teams) : '');

    $team2_id = getNotPlayedTeamId($teams, $team1_id);
    $team2_id = ( !$team2_id  ? getPlayedTeamId($teams, $team1_id) : '');

    // this is the dirty trick:
    // reset team2 battle index to '1'
    // decrement $i by 1, so this run did not exist
    // redo the run, now team2, should be a different one
    if ( alreadyPlayed($team1_id, $team2_id, $games) )
    {
        resetBattleIndex($team2_id, $teams);
        $i--;
    }
    else
    {
        $games[$game_count]['team1_id'] = $team1_id;
        $games[$game_count]['team2_id'] = $team2_id;
        resetBattleIndex($team1_id, $teams);
        resetBattleIndex($team2_id, $teams);
        $game_count++;
    }
}

var_dump($games);
?>

Dem Interpreter schmeckt das ； in den Schleifen nicht, also habe ich es mal rausgenommen. Außerdem habe ich 2 Schritte auskommentiert, da es die Funktion "getNextTeamId" nicht gibt. Wahrscheinlich liegt das Problem daran, aber ich steig da mittlerweile echt nicht mehr durch und habe Probleme das selbst zu korrigieren.
:rolleyes:

lockdoc · 3 Juni 2011

Ahh, ich hatte kurz noch was umgenannt und das getNextTeamId sollte eigentlich "getPlayedTeamId" heissen.

In den Funktion
getPlayedTeamId
getNotPlayedTeamId
resetBattleIndex

muessen die Bezeichnungen $teams und $team gleich sein, da gibt es 2 verschiedene.

Zudem sollte dafuer $team bzw $teams so aufgebaut sein
$team[0]['battle_index']
$team[0]['id']

martin · 3 Juni 2011

So habe die Änderungen gemacht und den nun aktuellen Code im obigen Beitrag aktualisiert. Soweit sogut, leider immer noch Endlosschleife.

lockdoc · 3 Juni 2011

die id muss bei 1 anfangen

martin · 3 Juni 2011

Ist jetzt auf 1, leider immer noch Endlosschleife.

lockdoc · 3 Juni 2011

Du musst das mal debugen (kein plan inwieweit das bei php geht).
Also kucken in welcher schleife er haengt und wie die werte dabei aussehen und warum

martin · 3 Juni 2011

Also er bleibt hängen, sobald $i = 1
Wenn ich ich die folgenden beiden Zeilen auskommentiere, läuft er durch:

//$games[$game_count]['team1_id'] = $team1_id;
//$games[$game_count]['team2_id'] = $team2_id;

er bleibt hängen, wenn wie gesagt $i = 1, $game_count=1 und $team1_id=1 $team2_id=0

lockdoc · 3 Juni 2011

Da liegt dann irgendwo der Fehler. $team2_id= sollte ja nicht auf 0 gesetzt werden duerfen.

Ich sehe grade nochwas.

Code:

 $team2_id = ( !$team2_id  ? getPlayedTeamId($teams, $team1_id) : '');

Da sollten eigentlich keine ' ' am Ende sein, sonst wird $team2_id auf ' ' gesetzt wenn es schon einen Wert hat. Also je nach php version entweder die ' ' weg oder anstelle dessen

Code:

 $team2_id = ( !$team2_id  ? getPlayedTeamId($teams, $team1_id) : $team2_id);

Bei dem anderen team1 genauso

martin · 3 Juni 2011

ohne ' ' meckert mein php, also habe ich es folgendermaßen korrigiert:

PHP:

    $team1_id = getNotPlayedTeamId($teams);
    $team1_id = ( !$team1_id ? getPlayedTeamId($teams) : $team1_id);

    $team2_id = getNotPlayedTeamId($teams, $team1_id);
    $team2_id = ( !$team2_id  ? getPlayedTeamId($teams, $team1_id) : $team2_id);

leider immern noch ohne erfolgt $team2_id wird wieder 0 bei $i=1

lockdoc · 3 Juni 2011

Na das bedeutet, dass getPlayedTeamId($teams, $team1_id) irgendwas falsch liefert.

du kannst ja mal folgendes machen und kucken

Code:

function getPlayedTeamId($teams, $except_id = 0)
{
    $offset = 0;
    $id        = 0;

    for ($i=0; $i<sizeof($teams); $i++)
    {
	echo "----------------------------------------------<br>";
	echo "i = $i<br>";
	echo "----------------------------------------------<br>";

        if ( $teams[$i]['battle_index'] > $offset && $teams[$i]['id'] != $except_id )
        {

	    echo "  ... in if, i= $i<br>";
            $id        = $teams[$i]['id'];
            $offset    = $teams[$i]['battle_index'];
	    echo "id = $id<br>";
	    echo "offset = $offset<br>";

        }
    }
    return ($id);
}

martin · 3 Juni 2011

0
----------------------------------------------
i = 0
----------------------------------------------
----------------------------------------------
i = 1
----------------------------------------------
... in if, i= 1
id = 1
offset = 1
----------------------------------------------
i = 2
----------------------------------------------
----------------------------------------------
i = 3
----------------------------------------------
----------------------------------------------
i = 4
----------------------------------------------
----------------------------------------------
i = 0
----------------------------------------------
... in if, i= 0
id = 0
offset = 1
----------------------------------------------
i = 1
----------------------------------------------
----------------------------------------------
i = 2
----------------------------------------------
----------------------------------------------
i = 3
----------------------------------------------
----------------------------------------------
i = 4
----------------------------------------------
0->1
0->0
1
----------------------------------------------
i = 0
----------------------------------------------
----------------------------------------------
i = 1
----------------------------------------------
... in if, i= 1
id = 1
offset = 1
----------------------------------------------
i = 2
----------------------------------------------
----------------------------------------------
i = 3
----------------------------------------------
----------------------------------------------
i = 4
----------------------------------------------
----------------------------------------------
i = 0
----------------------------------------------
... in if, i= 0
id = 0
offset = 1
----------------------------------------------
i = 1
----------------------------------------------
----------------------------------------------
i = 2
----------------------------------------------
----------------------------------------------
i = 3
----------------------------------------------
----------------------------------------------
i = 4
----------------------------------------------
1
----------------------------------------------
i = 0
----------------------------------------------
----------------------------------------------
i = 1
----------------------------------------------
... in if, i= 1
id = 1
offset = 1
----------------------------------------------
i = 2
----------------------------------------------
----------------------------------------------
i = 3
----------------------------------------------
----------------------------------------------
i = 4
----------------------------------------------
----------------------------------------------
i = 0
----------------------------------------------
... in if, i= 0
id = 0
offset = 1
----------------------------------------------
i = 1
----------------------------------------------
----------------------------------------------
i = 2
----------------------------------------------
----------------------------------------------
i = 3
----------------------------------------------
----------------------------------------------
i = 4
----------------------------------------------
1
----------------------------------------------
i = 0
----------------------------------------------
----------------------------------------------
i = 1
----------------------------------------------
... in if, i= 1
id = 1
offset = 1
----------------------------------------------
i = 2
----------------------------------------------
----------------------------------------------
i = 3
----------------------------------------------
----------------------------------------------
i = 4
----------------------------------------------
----------------------------------------------
i = 0
----------------------------------------------
... in if, i= 0
id = 0
offset = 1
----------------------------------------------
i = 1
----------------------------------------------
----------------------------------------------
i = 2
----------------------------------------------
----------------------------------------------
i = 3
----------------------------------------------
----------------------------------------------
i = 4
----------------------------------------------
1
----------------------------------------------
i = 0
----------------------------------------------
----------------------------------------------
i = 1
----------------------------------------------
... in if, i= 1
id = 1
offset = 1
----------------------------------------------
i = 2
----------------------------------------------
----------------------------------------------
i = 3
----------------------------------------------
----------------------------------------------
i = 4
----------------------------------------------
----------------------------------------------
i = 0
----------------------------------------------

....

Hier der Output

lockdoc · 3 Juni 2011

Beim 2. Durchlauf gibt "id" den Wert 0 aus.
Bist du sicher dass keines deiner Teams 0 als id benutzt?

Ansonsten musst du kucken ob die Groesse der Teams auch richtig berechnet wird etc.
Lass dir am besten mal alles ausgeben per schleife und vergleiche die Werte mit einem Schreibtisch Test (also gehe mal per Hand durch wie sie seien sollten), dann sollte sich der Fehler finden lassen

[PHP] Algorithmus gesucht für Spielplan

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Anfänger

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Wir schützen deine Privatsphäre