Help: schedule odd # of teams, arbitrary periods

[ron479]

I need help in scheduling head-to-head matchups where the number of teams is odd and the number of matchup periods is arbitrary. Each team must play the same number of matchups. For example, with 7 teams and 11 periods, the maximum number of matchups per team should be 8; any more will not fit.

Does anyone have an algorithm to generate a schedule with an odd number of teams where the number of periods is arbitrary?

Thanks,
Ron

[Ian Wakeling]

Ron,

I think a reasonable strategy for constructing the schedule is as follows:

(1) Decide on the basic parameters of the schedule.  There are at least three parameters, the number of teams (t), the number of rounds (r), and the number of matchups per round (k).  For a completely general schedule you would allow k to vary from round to round, this would handle the situation where a facility had been pre-booked by someone else, or where there was a short round in order to make up the right number of slots for an all-plays-all round robin.

(2) Decide all the matchups that you are going to play in the available slots.

(3) Place the matchups into a schedule at random, then move the matchups around by choosing the swaps that give the biggest improvement in some criterion that measure the 'niceness' of the schedule. The process may need to be repeated from different random starting positions.

I am not sure why you specifically mention an odd number of teams.  Clearly if you have 7 teams, and you want each team to play the same number of matches, then in step (1) you must choose the basic parameters so that there are a multiple of 7 slots in the schedule.

Does that help?

Ian.

[ron479]

Ian, that is quite helpful indeed, thanks. My first attempt at an algorithm did in fact involve iterative random distributions of matchups into available slots. I neglected to specify that each team can play only once per period ("game day").

I asked about an odd # of teams because the even case is trivial, since each team can play each period, and will thus end up playing a number of matchups equal to the number of periods.

Thanks,
Ron

[Ian Wakeling]

Ron,

Unfortunately, I assumed incorrectly that the number of slots was limited.  If you have (t-1)/2 slots per round, where t is odd, then you should base your plan on the standard all-plays-all round robin.  Following the schedules link above, you can obtain a schedule for an even number of teams,  simply delete one of the teams, removing all the matches they play in, to obtain the all-plays-all schedule for an odd number of teams, or use my Excel file which will do this for you.  As I hinted at above, the number of periods can no longer be arbitrary.For example here is an all-plays-all for 7 teams:

                   bye
(2 7) (3 6) (4 5)   1
(3 1) (4 7) (5 6)   2
(4 2) (5 1) (6 7)   3
(5 3) (6 2) (7 1)   4
(6 4) (7 3) (1 2)   5
(7 5) (1 4) (2 3)   6
(1 6) (2 5) (3 4)   7

There is the option to play either one third or two thirds of this schedule, however both involve playing one short round to make sure that each team gets the same number of matchups.

One third:         bye
(2 7) (3 6) (4 5)   1
(7 5) (1 4) (2 3)   6
(1 6)             23457

Two thirds:        bye
(2 7) (3 6) (4 5)   1
(7 5) (1 4) (2 3)   6
(3 1) (4 7) (5 6)   2
(6 4) (7 3) (1 2)   5
(1 6) (2 5)        347

To construct a schedule with exactly 8 matchups per team then you would need to start with the all-plays-all schedule for the first 7 rounds, preferably a different randomization that you could get with the Excel generator, and then add on the Two thirds schedule from above.  Be careful when you stitch the two parts together that you don't have the same team with two byes in a row.

I think that should help more than my initial reply

Ian.