I have an algorithm problem having to do with scheduling teams in rotation as fairly as possible.

Question

I have a project for school where I have to come up with an algorithm for scheduling 4 teams to play volleyball on one court, such that each team gets as close to the same amount of time as possible to play.

If you always have the winners stay in and rotate out the loser, then the 4th ranked team will never play and the #1 team always will. The goal is to have everybody play the same amount of time.

The simplest answer is team 1 play team 2, then team 3 play team 4 and keep switching, but then team 1 never gets to play team 3 or 4 and so on.

So I'm trying to figure out an algorithm that will allow everybody to play everybody else at some point without having one team sit out a lot more than any other team.

Suggestions?

Answer 1

pretend it's a small sports league, and repeat the "seasons"... (in most sports leagues in Europe, all teams play against all other teams a couple of times during a season)

Answer 2

well you should play 1-2 3-4, 1-3 2-4, 1-4 2-3 and then start all over again.

Answer 3

If there are N teams and you want all pairs of them to play once, then there are "N choose 2" = N*(N-1)/2 games you need to run.

To enumerate them, just put the teams in an ordered list and have the first team play every other team, then have the second team play all the teams below it in the list, and so on. If you want to spread the games out so teams have similar rest intervals between games, then see Knuth.

Answer 4

How about this: Make a hashtable H of size NC2, in this case, 6. It looks like:

H[12] = 0
H[13] = 0
H[14] = 0
H[23] = 0
H[24] = 0
H[34] = 0

I am assuming it would be trivial to generate the keys.

Now to schedule a game, scan through the hash and pick the key with the lowest value (one pass). The teams denoted by the key play the game and you increment the value by one.

EDIT: To add another constraint that no team should wait too long, make another hash W:

W[1] = 0
W[2] = 0
W[3] = 0
W[4] = 0

After every game increment the W value for the team that did not play, by one.

Now when picking up the least played team if there are more than one team combo with low play score, take help from this hash to determine which team must play next.

Answer 5

Check out the wikipedia entry on round robin scheduling.