On Aug 11, 9:23 am, "pushpen singh" <[EMAIL PROTECTED]> wrote:
> I have to schedule a league involving 16 teams.
> In the league all teams are going to play against all other teams.
> so there are going to be 120 matches all together.
>
> The leagues is divided into 15 phases of 8 matches each .
>
> In the one phase all teams are going to play one match each.
> so for 16 teams we will have 8 matches with the condition
> that if two teams have already played against each other
> in a previous phase they will not play against each other again.
>
> Please suggest some efficient algorithm for scheduling this.
> Also which team plays against which other team is decided
> randomly.
A simple rotation scheme is probably good enough for this problem. If
you start with A plays I; B plays J; ... H plays P, then just hold A
in the same place and rotate all the others. It's not very hard to
prove this works.
Here it is in C:
#include <stdio.h>
#define N 8
int main(void)
{
char matches[2][N] = {
"ABCDEFGH",
"IJKLMNOP"
};
int phase, i, t;
for (phase = 0; phase < 2*N - 1; phase++) {
printf("\nphase %2d:", phase + 1);
for (i = 0; i < N; i++)
printf(" [%c-%c]", matches[0][i], matches[1][i]);
t = matches[1][0];
matches[1][0] = matches[0][1];
for (i = 1; i < N - 1; i++)
matches[0][i] = matches[0][i + 1];
matches[0][N - 1] = matches[1][N - 1];
for (i = N - 1; i > 1; i--)
matches[1][i] = matches[1][i - 1];
matches[1][1] = t;
}
return 0;
}
Output:
phase 1: [A-I] [B-J] [C-K] [D-L] [E-M] [F-N] [G-O] [H-P]
phase 2: [A-B] [C-I] [D-J] [E-K] [F-L] [G-M] [H-N] [P-O]
phase 3: [A-C] [D-B] [E-I] [F-J] [G-K] [H-L] [P-M] [O-N]
phase 4: [A-D] [E-C] [F-B] [G-I] [H-J] [P-K] [O-L] [N-M]
phase 5: [A-E] [F-D] [G-C] [H-B] [P-I] [O-J] [N-K] [M-L]
phase 6: [A-F] [G-E] [H-D] [P-C] [O-B] [N-I] [M-J] [L-K]
phase 7: [A-G] [H-F] [P-E] [O-D] [N-C] [M-B] [L-I] [K-J]
phase 8: [A-H] [P-G] [O-F] [N-E] [M-D] [L-C] [K-B] [J-I]
phase 9: [A-P] [O-H] [N-G] [M-F] [L-E] [K-D] [J-C] [I-B]
phase 10: [A-O] [N-P] [M-H] [L-G] [K-F] [J-E] [I-D] [B-C]
phase 11: [A-N] [M-O] [L-P] [K-H] [J-G] [I-F] [B-E] [C-D]
phase 12: [A-M] [L-N] [K-O] [J-P] [I-H] [B-G] [C-F] [D-E]
phase 13: [A-L] [K-M] [J-N] [I-O] [B-P] [C-H] [D-G] [E-F]
phase 14: [A-K] [J-L] [I-M] [B-N] [C-O] [D-P] [E-H] [F-G]
phase 15: [A-J] [I-K] [B-L] [C-M] [D-N] [E-O] [F-P] [G-H]
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
