Re: Magic Scheduling Algorithms

hudsonfoods · Tue, 05 Jun 2001 23:44:43 -0700

Assuming that there are 2t teams, this will come
close to fairness. If it doesn't make sense (seeing as
it's nearly 2:00am and I'm really bad at proofreading
my own stuff anyway), reply here or email
me.

1) Split the teams into two equal divisions. I'll
call the teams A1 thru At and B1 thru Bt. Rooms will
be numbered R1 thru Rt (for now).

2) We'll
start with interdivisional play first. 
In round 1
in room Rn (n goes from 1 to t), team An will play
team Bn. 
Round 2, room Rn, A(n+1) vs.
B(n+2).
Round 3, room Rn, A(n+2) vs. B(n+4).
Round 4, room
Rn, A(n+3) vs. B(n+6).
And so on. (You can figure
out the formula for doing this -- I'm afraid of
making a "one-off" error if I write it out, though.
Also, if there are only 14 teams (for example), team
B19 should really be team B5. But you probably know
that.)

3a) If t is even: For the first t/2 matches, move the
match in room Rn to room R(n+1). As a result, round 1
will then have team At versus team Bt in room 1, A1
versus B1 in room 2, etc. (NB: After this shift, the
B-teams will have one interdivision game in each room.
The A-teams will have 1 room with 2 matches and 1
with none -- that's the best I can do.) 

3b) If
t is odd, delete round 1. (It will be made up
during the intradivisional portion of play.)

4)
Renumber the rooms as X1 thru X(t/2) and Y1 thru Y(t/2).
If there's a room left over (i.e., if t is odd),
re"number" it Z.

5) Hold two separate round robins.
Put division A in the X-rooms for odd-numbered rounds
of the round robin and the Y-rooms for the
even-numbered rounds of the round robin. Similarly, put
division B in the Y-rooms in odd rounds and the X-rooms in
even rounds.

5a) If t is even, use this
algorithm recursively to create two t-team round robins.
(NB: There is no such thing as a balanced 4-team round
robin -- one team will be in the same room all 3
matches.)

5b) If t is odd, have the teams on bye within their
division's round robins meet in room Z.

I've never
tried out the room-balancing aspects of this, but I
think it'll come close. If that fails, you can either
randomize the room frequency or use a greedy algorithm
(find the best room for each match, 1 at a
time).

Hope this helps!
--Keith