Round Robin Generator
Page 1 of 2 12 LastLast
Results 1 to 15 of 24

Thread: Round Robin Generator

  1. #1
    PHP Witch laserlight's Avatar
    Join Date
    Apr 2003
    Location
    Singapore
    Posts
    13,589

    Round Robin Generator

    If you've ever been involved in chess tournaments, you would know they come in various formats, one of which is the round robin format.
    In a round robin, each player plays every other player, and the difference in colours is kept to a minimum, with half the field having white for one more game than the other half.

    I couldnt come up with a good enough algorithm myself, so I sent an email to the webmaster of CERN's chess club, where they had a round robin pairing calculator available.
    The code was in pretty bad shape, but I managed to make out of the gist of the algorithm, and re-implemented it:
    PHP Code:
    <?php
    /************************************************
     * Round Robin Pairing Generator
     * Author: Eugene Wee
     * Date: 23 May 2005
     * Last updated: 23 May 2005
     * Copyright (c) 2005 Eugene Wee
     * Licensed under the Academic Free License 2.1
     * Based on algorithm by Tibor Simko
     ************************************************/

    function generateRoundRobinPairings($num_players) {
        
    //do we have a positive number of players? otherwise default to 4
        
    $num_players = ($num_players 0) ? (int)$num_players 4;
        
    //set number of players to even number
        
    $num_players = ($num_players == 0) ? $num_players $num_players 1;
        
    //format for pretty alignment of pairings across rounds
        
    $format "%0" ceil(log10($num_players)) . "d";
        
    $pairing "$format-$format ";
        
    //set the return value
        
    $ret $num_players " Player Round Robin:\n-----------------------";
        
    //print the rounds
        
    for ($round 1$round $num_players$round++) {
            
    $ret .= sprintf("\nRound #$format : "$round);
            
    $players_done = array();
            
    //print the pairings
            
    for ($player 1$player $num_players$player++) {
                if (!
    in_array($player$players_done)) {
                    
    //select opponent
                    
    $opponent $round $player;
                    
    $opponent += ($opponent 0) ? $num_players 1;
                    
    //ensure opponent is not the current player
                    
    if ($opponent != $player) {
                        
    //choose colours
                        
    if ($player == $opponent 2) {
                            if (
    $player $opponent) {
                                
    //player plays black
                                
    $ret .= sprintf($pairing$opponent$player);
                            } else {
                                
    //player plays white
                                
    $ret .= sprintf($pairing$player$opponent);
                            }
                        } else {
                            if (
    $player $opponent) {
                                
    //player plays white
                                
    $ret .= sprintf($pairing$player$opponent);
                            } else {
                                
    //player plays black
                                
    $ret .= sprintf($pairing$opponent$player);
                            }
                        }
                        
    //these players are done for this round
                        
    $players_done[] = $player;
                        
    $players_done[] = $opponent;
                    }
                }
            }
            
    //print the last pairing (i.e. for the last player)
            
    if ($round == 0) {
                
    $opponent = ($round $num_players) / 2;
                
    //last player plays white
                
    $ret .= sprintf($pairing$num_players$opponent);
            } else {
                
    $opponent = ($round 1) / 2;
                
    //last player plays black
                
    $ret .= sprintf($pairing$opponent$num_players);
            }
        }
        return 
    $ret;
    }
    ?>
    In my case, I'm using it as:
    PHP Code:
    $n 4;
    if (!empty(
    $_GET['n']) && ctype_digit($_GET['n'])) {
        
    $n $_GET['n'];
    }
    echo 
    '<pre>' generateRoundRobinPairings($n) . '</pre>'
    In "roundrobin.php", and so goto roundrobin.php?n=8 if I want 8 players.
    Last edited by laserlight; 05-23-2005 at 08:32 AM.
    Use Bazaar for your version control system
    Read the PHP Spellbook
    Learn How To Ask Questions The Smart Way

  2. #2
    PHP Witch laserlight's Avatar
    Join Date
    Apr 2003
    Location
    Singapore
    Posts
    13,589

    Updated Version

    Wow, it has been nearly two years since I posted my code. At a whim, I decided to look again and see if I could make any improvements after two years, and I think I have. The function can be used in the same way as originally described:
    PHP Code:
    /******************************************************************************
     * Round Robin Pairing Generator
     * Author: Eugene Wee
     * Date: 23 May 2005
     * Last updated: 13 May 2007
     * Based on an algorithm by Tibor Simko.
     *
     * Copyright (c) 2005, 2007 Eugene Wee
     *
     * Permission is hereby granted, free of charge, to any person obtaining a copy
     * of this software and associated documentation files (the "Software"), to deal
     * in the Software without restriction, including without limitation the rights
     * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
     * copies of the Software, and to permit persons to whom the Software is
     * furnished to do so, subject to the following conditions:
     *
     * The above copyright notice and this permission notice shall be included in
     * all copies or substantial portions of the Software.
     *
     * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
     * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
     * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
     * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
     * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
     * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
     * THE SOFTWARE.
     ******************************************************************************/

    function generateRoundRobinPairings($num_players) {
        
    // Do we have a positive number of players? If not, default to 4.
        
    $num_players = ($num_players 0) ? (int)$num_players 4;

        
    // If necessary, round up number of players to nearest even number.
        
    $num_players += $num_players 2;

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

        
    // Set the return value
        
    $ret $num_players " Player Round Robin:\n-----------------------";

        
    // Generate the pairings for each round.
        
    for ($round 1$round $num_players$round++) {
            
    $ret .= sprintf("\nRound #$format : "$round);
            
    $players_done = array();

            
    // Pair each player except the last.
            
    for ($player 1$player $num_players$player++) {
                if (!
    in_array($player$players_done)) {
                    
    // Select opponent.
                    
    $opponent $round $player;
                    
    $opponent += ($opponent 0) ? $num_players 1;

                    
    // Ensure opponent is not the current player.
                    
    if ($opponent != $player) {
                        
    // Choose colours.
                        
    if (($player $opponent) % == xor $player $opponent) {
                            
    // Player plays white.
                            
    $ret .= sprintf($pairing$player$opponent);
                        } else {
                            
    // Player plays black.
                            
    $ret .= sprintf($pairing$opponent$player);
                        }

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

            
    // Pair the last player.
            
    if ($round == 0) {
                
    $opponent = ($round $num_players) / 2;
                
    // Last player plays white.
                
    $ret .= sprintf($pairing$num_players$opponent);
            } else {
                
    $opponent = ($round 1) / 2;
                
    // Last player plays black.
                
    $ret .= sprintf($pairing$opponent$num_players);
            }
        }

        return 
    $ret;

    Aside from arithmetic simplifications and cosmetic changes to comments and spacing, the main change is the use of PHP's xor operator to simplify the colour selection code. Oh, and I decided to switch to the MIT/Expat license, which unfortunately increased the length of the code.
    Use Bazaar for your version control system
    Read the PHP Spellbook
    Learn How To Ask Questions The Smart Way

  3. #3
    phpMaster
    Join Date
    Jun 2005
    Location
    Europe
    Posts
    2,983


    hi laser

    you know i play chess .. good chess

    if you remember i had a look at some FEN chess appication you had written
    we had some contact via Instant Messenger
    I know you write good scripts!

    This tournament set up feature - make a round robin - in your latest post.

    1. Does it work as standalone ? Or is it only API utility to include in other pages?
    2. Can I just copy and RUN it at my server ( http://okay.mine.nu ) ? As it is?


    thanks
    mattafort

  4. #4
    PHP Witch laserlight's Avatar
    Join Date
    Apr 2003
    Location
    Singapore
    Posts
    13,589
    I would hardly call a single function an API. You can copy it along with the snippet of one way to use it that is in my first post.
    Use Bazaar for your version control system
    Read the PHP Spellbook
    Learn How To Ask Questions The Smart Way

  5. #5
    phpMaster
    Join Date
    Jun 2005
    Location
    Europe
    Posts
    2,983
    okay i will try
    install it in my php development part of my server
    and do some testruns



    I will be back with Code Critique
    because is the function of this phpbuilder board category

    Sometimes critique in here is so heavy and upright
    ... without any due credits or compliments to balance critique
    ... that people only post code here ONCE
    ... never comes back again
    ... and most probably go elsewhere
    If they can find any other PHP Scrits Website/Forum.
    You think they can ???

    Are there any other sites for discussing php scripts and coding ...?


    Be Back soon with comments to your script, within max 2-3 days
    Regards
    halojoy

  6. #6
    phpMaster
    Join Date
    Jun 2005
    Location
    Europe
    Posts
    2,983
    hi

    to be able to quickly and easy compare your 2005 function version
    with the new 2007 version
    I setup this roundrobin.php
    It is for most PHP coders self-explaining, I hope
    PHP Code:
    <?php

    $n 
    4;           // number of players in tournament
    $functions 2;   // total number of versions of this function

    if (isset($_GET['n']) && !empty($_GET['n']) && ctype_digit($_GET['n'])) {
        
    $n $_GET['n'];
    }
    if ( 
    $n 40 )
        
    $n 40;

    $f $functions;
    if (isset(
    $_GET['f']) && !empty($_GET['f']) && ctype_digit($_GET['f'])) {
        
    $f $_GET['f'];
    }
    if ( 
    $f $functions || $f 
        
    $f $functions;

    // include and run function, using values of $f and $n
    include "func.generate-rr$f.php";

    echo 
    "generateRoundRobinPairings($n);<br>\n";
    echo 
    "Version: $f<br>\n";
    echo 
    '<pre>' generateRoundRobinPairings($n) . '</pre>';

    ?>

    Files, all in same web folder:
    func.generate-rr1.php ---- 2005 version include
    func.generate-rr2.php ---- 2007 version include
    roundrobin.php ------- main script


    How to use:
    URL/roundrobin.php?n=8&f=2
    ... where n= number of players ( max 40 players )
    ... if no value of n, 4 players ( like in original roundrobin.php, see Post #1 )
    ... and f= function version ( 1=2005, 2=2007 );
    ... if no value of f, the latest version will be used=highest number=total number of version



    halojoy
    Last edited by halojoy; 05-13-2007 at 11:13 AM.

  7. #7
    Junior Member
    Join Date
    Nov 2009
    Posts
    2

    round-robin algorithm

    I found this link of a tutorial on creating a schedule with a round robin algorithm. Looks pretty good. The link is http://kevinmusselman.com/blog/2009/...bin-algorithm/

  8. #8
    Junior Member
    Join Date
    Jun 2010
    Posts
    12
    i have teams which i want to distribute in a schedule , each team play with the others one time and each team play once a day .
    i got teams' names and its number from the database.

    Q: i want to make daily schedule for matches (like the daily schedule of world cup)
    and to enter each date in the database with the schedule of this date.

    please follow this link to see what i need:
    http://www.teamopolis.com/tools/roun...generator.aspx

  9. #9
    PHP Witch laserlight's Avatar
    Join Date
    Apr 2003
    Location
    Singapore
    Posts
    13,589
    ragy, you are free to modify my code to suit your needs, subject to the license. If you need help for the modification, please ask in another forum, e.g., Coding.
    Use Bazaar for your version control system
    Read the PHP Spellbook
    Learn How To Ask Questions The Smart Way

  10. #10
    Junior Member
    Join Date
    Nov 2011
    Posts
    1
    This is my version.

    I tried to implement what wikipedia says on http://en.wikipedia.org/wiki/Round-r...ling_algorithm

    I've attached a image with the explanation of the algorithm for 8 players.

    PHP Code:
      function round_robin($num_teams 8)
      {
        
    $num_rounds $num_teams 1;
        
        
    $rounds = array();
        
        for(
    $round 0$round $num_rounds$round++) {      
          for (
    $index 0$index $num_teams 2$index++)
          {
            
    $local_key = ($index != 0) * ($index $round) + 
              ((
    $index != 0) && (($index != 0) * ($index $round) <= 0)) * $num_rounds;
            
            
    $away_key $num_rounds $index $round 
              ((
    $index != 0) && ($num_rounds $index $round <= 0)) * $num_rounds;
            
            
    $rounds[$round][] = array($local_key$away_key);
          }
        }

        return 
    $rounds;
      } 
    Attached Images Attached Images

  11. #11
    Junior Member
    Join Date
    Apr 2012
    Posts
    7
    Hi,

    I created a roundrobin function from scratch as i thought it might be easier to get the same results and also allowing me to use arrays filled with strings directly instead of numbers.

    Because i pull a list of names from a database and add into an array i can now schedule this directly with below function. No extra step needed to link numbers to names etc.

    Please feel free to try it and if it works then leave a comment.
    I also have a version which allows for 2 way (home & return) schedule and or shuffle option. If somone is interested in that one then leave a coment as well.

    PHP Code:
    <?php

    /**
     * @author D.D.M. van Zelst
     * @copyright 2012
     */

    function scheduler($teams){
    // Check for even number or add a bye
        
    if (count($teams)%!= 0){
            
    array_push($teams,"bye");
        }
    // Splitting the teams array into two arrays
        
    $away array_splice($teams,(count($teams)/2));
        
    $home $teams;
    // The actual scheduling based on round robin
        
    for ($i=0$i count($home)+count($away)-1$i++){
            for (
    $j=0$j<count($home); $j++){
                
    $round[$i][$j]["Home"]=$home[$j];
                
    $round[$i][$j]["Away"]=$away[$j];
            }
    // Check if total numbers of teams is > 2 otherwise shifting the arrays is not neccesary
            
    if(count($home)+count($away)-2){
                
    array_unshift($away,array_shift(array_splice($home,1,1)));
                
    array_push($home,array_pop($away));
            }
        }
        return 
    $round;
    }
    ?>
    How to use, for example create an array like:
    PHP Code:
    <?php $members = array(1,2,3,4); ?>
    or
    PHP Code:
    <?php $members = array("name1","name2","name3","name4"); ?>
    then call the function to create your schedule based on above array:
    PHP Code:
    <?php $schedule scheduler($members); ?>
    To display the resulted array schedule simply do like below or anyway you like:
    This little code displays the schedule in a nice format but use it anyway you like.

    PHP Code:
    <?php
    foreach($schedule AS $round => $games){
        echo 
    "Round: ".($round+1)."<BR>";
        foreach(
    $games AS $play){
            echo 
    $play["Home"]." - ".$play["Away"]."<BR>";
        }
        echo 
    "<BR>";
    }
    ?>
    Leave a note if it worked for you or if you are interested in the 2-way version with shuffle.

    Dave
    Last edited by bradgrafelman; 04-27-2012 at 02:10 AM. Reason: posts merged

  12. #12
    Pedantic Curmudgeon Weedpacket's Avatar
    Join Date
    Aug 2002
    Location
    General Systems Vehicle "Thrilled To Be Here"
    Posts
    21,910
    Quote Originally Posted by davaze
    Please feel free to try it and if it works then leave a comment.
    Even without running it I can leave a comment/critique; you didn't read the rules....
    THERE IS AS YET INSUFFICIENT DATA FOR A MEANINGFUL ANSWER
    FAQs! FAQs! FAQs! Most forums have them!
    Search - Debugging 101 - Collected Solutions - General Guidelines - Getting help at all

  13. #13
    Junior Member
    Join Date
    Apr 2012
    Posts
    7
    Sorry,

    I guess you mean the indention for the code. Forgot to do.
    Can i still edit the post to update the indention?

    Thanks

  14. #14
    Junior Member
    Join Date
    May 2012
    Posts
    1

    Smile

    This works fine, with one exception. The script does not account for team playing home AND away. You have Team 1 home EVERY week.

    Can you adjust it so each week a team is home, then away, then back home again, etc; ?


    Quote Originally Posted by davaze View Post
    Hi,

    I created a roundrobin function from scratch as i thought it might be easier to get the same results and also allowing me to use arrays filled with strings directly instead of numbers.

    Because i pull a list of names from a database and add into an array i can now schedule this directly with below function. No extra step needed to link numbers to names etc.

    Please feel free to try it and if it works then leave a comment.
    I also have a version which allows for 2 way (home & return) schedule and or shuffle option. If somone is interested in that one then leave a coment as well.

    PHP Code:
    <?php

    /**
     * @author D.D.M. van Zelst
     * @copyright 2012
     */

    function scheduler($teams){
    // Check for even number or add a bye
        
    if (count($teams)%!= 0){
            
    array_push($teams,"bye");
        }
    // Splitting the teams array into two arrays
        
    $away array_splice($teams,(count($teams)/2));
        
    $home $teams;
    // The actual scheduling based on round robin
        
    for ($i=0$i count($home)+count($away)-1$i++){
            for (
    $j=0$j<count($home); $j++){
                
    $round[$i][$j]["Home"]=$home[$j];
                
    $round[$i][$j]["Away"]=$away[$j];
            }
    // Check if total numbers of teams is > 2 otherwise shifting the arrays is not neccesary
            
    if(count($home)+count($away)-2){
                
    array_unshift($away,array_shift(array_splice($home,1,1)));
                
    array_push($home,array_pop($away));
            }
        }
        return 
    $round;
    }
    ?>
    How to use, for example create an array like:
    PHP Code:
    <?php $members = array(1,2,3,4); ?>
    or
    PHP Code:
    <?php $members = array("name1","name2","name3","name4"); ?>
    then call the function to create your schedule based on above array:
    PHP Code:
    <?php $schedule scheduler($members); ?>
    To display the resulted array schedule simply do like below or anyway you like:
    This little code displays the schedule in a nice format but use it anyway you like.

    PHP Code:
    <?php
    foreach($schedule AS $round => $games){
        echo 
    "Round: ".($round+1)."<BR>";
        foreach(
    $games AS $play){
            echo 
    $play["Home"]." - ".$play["Away"]."<BR>";
        }
        echo 
    "<BR>";
    }
    ?>
    Leave a note if it worked for you or if you are interested in the 2-way version with shuffle.

    Dave

  15. #15
    Senior Member Derokorian's Avatar
    Join Date
    Apr 2011
    Location
    Denver
    Posts
    1,790
    Also what if two teams face each other that were both home teams the previous round? This is why the higher ranked team (aka team 1) would keep home field advantage.
    Sadly, nobody codes for anyone on this forum. People taste your dishes and tell you what is missing, but they don't cook for you. ~anoopmail
    I'd rather be a comma, then a full stop.
    User Authentication in PHP with MySQLi - Don't forget to mark threads resolved - MySQL(i) warning

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •