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

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

Answer 2

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 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

Check out the wikipedia entry on round robin scheduling.

Answer 5

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 6

The REQUIREMENTS for the BALANCED ROUND ROBIN algorithm, for the Team championship scheduling may be found here: Constellation Algorithm - Balanced Round Robin The requirements of the algorithm can be defined by these four constraints:

1) All versus all Each team must meet exactly once, and once only, the other teams in the division/ league. If the division is composed of n teams, the championship takes place in the n-1 rounds.

2) Alternations HOME / AWAY rule The sequence of alternations HOME / AWAY matches for every teams in the division league, should be retained if possible. For any team in the division league at most once in the sequence of consecutive matches HAHA, occurs the BREAK of the rhythm, i.e. HH or AA match in the two consecutive rounds.

3) The rule of the last slot number The team with the highest slot number must always be positioned in the last row of the grid. For each subsequent iteration the highest slot number of grid alternates left and right position; left column (home) and right (away). The system used to compose the league schedule is "counter-clockwise circuit." In the construction of matches in one round of the championship, a division with an even number of teams. If in a division is present odd number of teams, it will be inserted a BYE/Dummy team in the highest slot number of grid/ring.

4) HH and AA non-terminal and not initial Cadence HH or AA must never happen at the beginning or at the end of the of matches for any team in the division.

友情链接