11

I'll start of by saying that I understand that this topic is complicated and that there probably isn't an easy answer. If it were easy then everybody would be doing it. That being said...

I've been asked to build an application to manage a sports league. Most of the concepts are fairly easy to understand except for this one: How to generate a schedule of play where there are no overlaps (team plays 2 teams at once), where a team in a division plays its teams twice but plays teams from the other divisions once, and makes sure that there are no holes in the schedule (each team plays every week)

Right now the process is done manually using a rosetta stone type spreadsheet that I've built to serve this purpose, but it only works for the number of teams it was designed for. I have variations made for 30 teams, 24 teams and 28 teams. Rather than continually attempt to readjust my translation table, I'd like to be able to codify that logic and tweak that process instead.

Thoughts?

5 Answers 5

14

There is a pretty straightforward system used in e.g. chess tournaments called round-robin.

The idea is to divide the players to the two sides of a table. One of the players is designated as a "hub" (for a want of a better word). The tournament starts by having players facing each other playing against each other. After the first round everyone but the hub move one chair forward and the white/black (home/away in sports) order is switched. The entire round-robin competition is finished when the players sit in their original places. If you want everyone to play everyone twice just do the same again.

Wikipedia article with implementation details.

In your special case I would try doing the round robin once including all teams. Then you do the same for each division once and to make sure teams within divisions play each other once at home and once away, check from the first round robin what way the teams played in that round.

The down-side of this is, of course, that you will play all inter-division matches well before the tournament finishes (since the last n-1 matches are against intra-division teams [n=number of teams in division]). If this is a problem you could simply swap matches around a bit.

I actually wrote a simple Python script that does this. It didn't take many lines of code and produced pretty good results. This will create a schedule where each team plays each team in their division twice and once against teams in other divisions. There is no check to make sure that the teams meet each other twice in such a way that the same team is at home, however. But this code should give a good idea on how to create your own scheduling code.

#!/usr/bin/python

div1 = ["Lions", "Tigers", "Jaguars", "Cougars"]
div2 = ["Whales", "Sharks", "Piranhas", "Alligators"]
div3 = ["Cubs", "Kittens", "Puppies", "Calfs"]

def create_schedule(list):
    """ Create a schedule for the teams in the list and return it"""
    s = []

    if len(list) % 2 == 1: list = list + ["BYE"]

    for i in range(len(list)-1):

        mid = int(len(list) / 2)
        l1 = list[:mid]
        l2 = list[mid:]
        l2.reverse()    

        # Switch sides after each round
        if(i % 2 == 1):
            s = s + [ zip(l1, l2) ]
        else:
            s = s + [ zip(l2, l1) ]

        list.insert(1, list.pop())

    return s


def main():
    for round in create_schedule(div1):
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div2):
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div3): 
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div1+div2+div3): 
        for match in round:
            print match[0] + " - " + match[1]
        print

if __name__ == "__main__":
    main()
13

There are two algorithms, one for odd teams, one for even teams to make sure the round robin happens.

I am going to generate you a graphic if i can.

ODD # of teams

The algorithm is to rotate all the teams clockwise. If we had 5 teams:

1 2 --> 3 1 --> 5 3 --> 4 5 --> 2 4
3 4     5 2     4 1     2 3     1 5
5       4       2       1       3   

At this point we have completed one round robin where everyone plays each other once... the next round would again be..

1 2
3 4
5

EVEN # of teams

When we have an even number of teams, you do the same rotation, except you hold team #1 in fixed position and rotate all the other teams around #1 in a clockwise fashion. So, if we had 4 teams..

1 2 --> 1 3 --> 1 4 
3 4     4 2     2 3 

This would be one complete round robin... the next match up would be..

1 2 
3 4 

Programmatically, There's a few ways you could approach this.

3
  • Thanks @Jas Panesar! Your 2-list-approach helped me to fix an issue I had with my previous algorithm and it made my code much simpler.
    – ultimate
    Mar 21, 2022 at 12:51
  • 1
    @ultimate Glad it helped! Sometimes manual algorithms without computers port very nicely to simple functions that can be maintained and understood by others. Jan 1 at 21:21
  • I owe you one! I tried it with combinatorics (n choose k), which yielded all the pairings, but not in such a nice balanced way (every iteration yields pairings for all teams). Jul 27 at 7:31
3

I would just encode these constraints as a boolean formula and use some SAT-solver to obtain solutions (e.g. MiniSAT for C++, SAT4J for Java, and you could even write you own simple solver). The input to these solvers is standartized by DIMACS.

See also "A SAT Encoding for the Social Golfer Problem" and "A SAT Based Scheduler for Tournament Schedules" for SAT-encodings of similar problems.

2

here's a shot at an implementation

public interface ITeam
{
   bool PlaysOn(DateTime date);
   bool canPlay(ITeam); //returns true if a game between the teams is legal (played once/twice   
                        //already, same different divisions and other applicable rules
}

IEnumerable<ITeam> teams = null; //replace with initialization
IEnumerable<ITeams> reversed = team.Reverse();
IEnumerable<DateTIme> gameDays = null;//replace with initialization
var count = teams.Count();

foreach(var date in gameDays)
{
   for(int i = 0;i<count;i++)
   {
      var innerTeams = i % 2 == 0 ? teams : reversed;
      var team = (from t in innerTeams
                  where !t.PlaysOn(date)
                  select t).First();  
      var opp = (from t in teams
                 where !t.PlaysOn(date) && t.CanPlay(team)
                 select t).First();
      SetupGame(team,opp);
   }
} //lot of optimazation possible :)

I've only tested it on paper but for my setup it works. By alternating between starting at the start of the teams list and the end of the list I avoid the situations where the same team would have to play the same team over and over again (or repeatedly play on the same day) in my paper test I represented every possible encounter as a different opponnent but that's basically what the CanPlay method should do. Hope this helps, eventhough it not a complete solution

0

Here's my solution in Clojure, implementing the suggestion of Jas Panesar.

(defn rotate
  "Creates a new vector with the first element put at its end."
  [v]
  (if (or (empty? v) (= (count v) 1))
    v
    (let [head (first v)
          tail (rest v)]
      (flatten (vector tail head)))))

(defn pair-up
  "Pairs up each of the given teams against each other."
  ([teams]
   (let [anchor (first teams)
         remainder (rest teams)
         phases (count remainder)
         wheel (take phases (iterate rotate remainder))
         rotated-teams (map #(flatten (vector anchor %)) wheel)]
     (map #(partition 2 %) rotated-teams))))

And here is how to use it in the REPL:

> (pair-up [:a :b :c :d])
(((:a :b) (:c :d)) ((:a :c) (:d :b)) ((:a :d) (:b :c)))

> (pair-up [:a :b :c :d :e :f])
(((:a :b) (:c :d) (:e :f))
 ((:a :c) (:d :e) (:f :b))
 ((:a :d) (:e :f) (:b :c))
 ((:a :e) (:f :b) (:c :d))
 ((:a :f) (:b :c) (:d :e)))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.