phptournamentmatchmakingsports-league-scheduling-problem

League Scheduling without RoundRobin


currently I am actually looking for a term specific for my problem:

I've created a league of >4 Teams The League lasts 3 Rounds (Numbers for the sake of simplicity) Matchups shall be assigned randomly out of Teams a Team has not yet played against.

I am struggling to get my current code running with each fringe case so I'd like to look up 'standard' algorythm developed for such cases, but I cannot come up with the term I am looking for.

One Schedule Example would be:

TeamA: C,E,B
TeamB: F,H,A
TeamC: A,D,H
TeamD: G,C,F
TeamE: H,A,G
TeamF: B,G,D
TeamG: D,F,G
TeamH: E,B,C

I couldn't find anything in that regard, as it seems to be a very, very unlikely thing to be used in leagues/tournaments - however that's my requirement.

This is my current code which creates ONE Round. It may happen, that this code won't give each a team an opponent in round 3 as their possible opponents have a matchup already assigned this round (tested with 6 teams, may occur in Round3)

 public function CalculateDivision()
{
     $teams = Division::find(1)->teams()->get();
     $diffs = array();
     foreach($teams as $team)
     {
//Get possible Opponents
         $opp = Division::find(1)->teams()->where('id','!=',$team->id)->lists('id');
         $matches = $team->matches()->get();
         $plyd = array();
         foreach($matches as $match)
         {   
//Find Opponents a team already has played against
             $plyd[] = $match->teams()->where('id','!=',$team->id)->pluck('id');    

         }
//Substract Opponents already played against from possible Opponents
         $TBP = array_diff($opp,$plyd);
         $diffs[$team->id] = $TBP;
     }
//Order By Least possible Opponents possible
     asort($diffs);
     $this->CalculateMatches($diffs);
}

private function CalculateMatches($teams)
{
//$teams equals $teams[teamID] = [Opponent1ID,Opponent2ID ...]
    $setTeams = array();
    foreach($teams as $key => $team)
    {
//If Team hasn't already a new matchup find opponent from their possible opponent array
        if(!in_array($key,$setTeams))
        {
           shuffle($team);
           foreach($team as $opponent)
           {
//If possible opponent hasn't already a matchup create one, add both teams to 'has already a match' so the loop doesn't evaluate them again
               if(!in_array($opponent,$setTeams))
               {
                   $this->CreateMatch($key,$opponent);
                   $setTeams[] = $key;
                   $setTeams[] = $opponent;
                   break;    
               }
           }
        }
    }
}

Any help for what I shall google would be appreciated


Solution

  • A Swiss system "is a non-eliminating tournament format which features a predetermined number of rounds of competition, but considerably fewer than in a round-robin tournament".

    It's widely used in chess and other games. According to Wikipedia:

    Swiss systems are commonly used in chess, bridge, eSports, Morabaraba, Scrabble, Backgammon, squash, Pétanque (boules), Quiz bowl, Magic: The Gathering, Policy Debate, Warhammer, eight-ball, Reversi, Dominion, Pokémon TCG, Yu-Gi-Oh, Blood Bowl, Guild Wars 2, Star Wars: X-Wing Miniatures Game, Path of Exile and Android: Netrunner.

    It may fit your needs, and you can find some ready-to-use implementation.