Help creating a schedule generator

Question

I am working on a programming exercise that has interested me for some time. The goal of this exercise is to generate a softball schedule for a seasons programatically. What I am looking for is general advice rather than a specific anwser as I am trying to learn something in the process.

The part of the program I am really struggling with is how to generate all of the games that are played in one night. This is the basic functionality I am trying to achieve in the first interation.

Problem: Given a list of teams, generate a schedule that has every team play 2 games, and no team can play the same team twice in one night.

Answer 1

It seems like you could do this quite simply by just rotating your team list.

e.g. given teams 1..10, do this:

Team A: 1  2  3  4  5  6  7  8  9 10
Team B: 2  3  4  5  6  7  8  9 10  1

so in game one, team A plays team B. For game two, rotate again:

Team A: 1  2  3  4  5  6  7  8  9 10
Team B: 3  4  5  6  7  8  9 10  1  2

Nine games will give you a full round-robin, and then you can start at the beginning again. Take the games in pairs for your nightly matchups.

EDIT

Kylotan points out that this doesn't actually work, as it has every team playing twice at once. Oops. If you came up with something that genuinely works, I encourage you to post it and accept it :-)

Answer 2

Use this kind of circulation. You keep the teams in a ring and rotate the ring around.

Team A:  1 2 3
Team B:  4 5 6

Team A:  4 1 2
Team B:  5 6 3

Team A:  5 4 1 
Team B:  6 3 2

Team A:  6 5 4
Team B:  3 2 1

Team A:  3 6 5
Team B:  2 1 4

Answer 3

The following solution might not be the best, but see if it works for you.

I start by creating a structure to hold each Game

public struct Game {
   private int TeamA;
   private int TeamB;
   private bool GamePlayed;

   // I am adding this to quickly see what team is playing. I used this for debugging
   // purposes to make sure the same team doesn't play another team twice.
   public override ToString() {
      return TeamA.ToString() + " vs. " + TeamB.ToString(); 
   }
}

Then I create a List that comtains all the different combinations of 10 teams playing each other. There should be 45.

List<Game> AllGamesInSchedule = new List<Game>();

for (int i = 1; i <= 10; i++) {
    for (int j = (i + 1); j <= 10; j++) {
        AllGamesInSchedule.Add(new Game(i, j));
    }
}

// This prints all the different game combinations out to the console to see
// that they are all different.
foreach (Game game in AllGamesInSchedule) {
    Console.WriteLine(game.ToString());
}

Now you can create a method that picks games out of this List. Once a game is picked out, change the GamePlayed field to true to know that you shouldn't pick this match again. Or you could just remove the game from the list.

You said you wanted guidance and that is why I didn't create the method to pick games out.

Hopes this helps.

Answer 4

I went with the implementation that I found on Wikipedia for Round Robin http://en.wikipedia.org/wiki/Round-robin%5Ftournament

The standard algorithm for round-robins is to assign each competitor a number, and pair them off in the first round …

  1  2  3  4  5  6  7  
  14 13 12 11 10 9  8

… then fix one competitor (number one in this example) and rotate the others clockwise …

 1  14 2  3  4  5  6
 13 12 11 10 9  8  7


 1  13 14 2  3  4  5
 12 11 10 9  8  7  6

… until you end up almost back at the initial position

 1  3  4  5  6  7  8
 2 14  13 12 11 10 9