Round Robin Tournament Scheduling
Schedules - You must register to Post and Download => Requests => Topic started by: inforeports on October 27, 2010, 01:16:35 PM
-
I really don't know what to call this script I am trying to create so I call it a Hybrid Round Robin. What I am trying to accomplish is creating a script that is a cross between a round-robin and a double header round robin.
Scenario:
This is a league where on average every team plays 3 games every two weeks. Obviously a team cannot play a 1/2 of a game, so they must play 2 games one week and 1 game the next. I also cannot have any repeats over the course of the schedule.
I have successfully create a rr and a dhrr. But this is killing me. IS there anyone who can direct me with this or give me a clue as to how I might solve this problem.. I am using PHP as a language.
-
Is this a game where the same two teams would compete several times in a row like baseball (maybe it is baseball)? Is there more than one division where one team doesn't meet as many or as often opponents outside its division? Can you just play the first three rounds in the first two week period, repeating until the end of the regular season? Are there a pair of simultaneous games every week with a third of the teams sitting out in any time slot? How many teams/divisions?
Just need a little more info to suggest something.
-
It is a softball league. We have a league of 28 teams but it could be more or less and we have a softball complex where we have 7 diamonds available. So each diamond could be looked at like a venue. Plus there are four time slots for each diamond. Thus, each diamond can host four games. Here is a match up that could happen on diamond 1.
Diamond 1:
1 2
2 3
3 4
4 5
Team 1 & 5 cannot play the rest of the night. They will need to play 2 games the next week and the other teams (2,3,4) need to play only 1 game the next week. At the end of the season all the teams have to play the same number of games, BUT, they will not play every team as the season is not long enough.
I have been having problems even though I have enough match ups my algorithm wants to keep using teams that have already played.
I hope I clarified a little more.
-
As far as the number of divisions, there could be 1,2,3 or 4 depending on the number of teams. No team sits any week unless the number of teams and match-up suggests that there should be a bye.
-
If you started with a standard round robin for 28 players (for example by following the schedules button near the top of the screen), could this be manipulated to give a suitable schedule? Play the first two rounds in week 1, specifically round 1 matches 1-7 in time slot 1, round 1 matches 8-14 in time slot 2, round 2 matches 1-7 in time slot 3 and round 2 matches 8-14 in times slot 3. This gives everyone two match-ups in the first week, most will have a rest period in between. In the second week give everyone just one match by using round 3 from the standard schedule and the first two time slots. Continue like this alternating one week with two matches, the next week wtih one.
Your example works well since 7 diamonds divides into 28. For other situations you may need to modify your algorithm to start with a standard schedule, take as many rounds as you want to play in the season, then rearrange the match-ups to fit the 7 diamond & 4 slot format. At least this would avoid the repeated pairing problem and give every team and the same number of matches.
Or have I missed the point? Being a Brit I am not familiar with Softball. Is it essential that the two matches on the same night are played in consecutive time slots?
Hope that helps.
-
Is it essential that the two matches on the same night are played in consecutive time slots?
Yes.. The league does not want a team to have to sit around. The type of sport really doesn't matter it is just the algorithm I am trying to figure out. Right now I am using a grid filled with '1's and '0's. Half of the grid is filled with ones as I have eliminated the duplicate matchups the remaining match ups have '0's. then I start finding matchups that I can use for the schedule. As I pick a matchup from the grid then I mark it with a '1'. Thus that matchup cannot be used again. The problem I am having is with my constraints and they way I search the grid I still come up with matches that have been used and thus the time slots are filled with blanks. I feel like I need some way of going through the matchups that is able to find them other than a loop but I don't know what that would be or how it would be implemented.
I hope this helps:
| T | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 3 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 4 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 5 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 6 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 11 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 12 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 13 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 14 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 15 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 16 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 17 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 18 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 19 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 20 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 21 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 22 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 23 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 24 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 25 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 26 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 27 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 28 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
Here is part of the routine I use to find matchups the function 'check_team' is the routine that checks against constraints and returns true or false:
function find_match(&$grid, $team=NULL){
global $teams;
global $used;
$mu = array();
if($team==NULL){
$team=1;
}
for($row=1; $row<=$teams; $row++){
for($col=1; $col<=$teams; $col++){
if($grid[$row][$col]<>1){
if($col==$team && check_team($row)){
//echo($row . "-" . $col . " col<br>");
$grid[$row][$col] = 1;
$mu[]=$col;
$mu[]=$row;
break 2;
}elseif ($row==$team && check_team($col)){
//echo($row . "-" . $col . " row<br>");
$grid[$row][$col] = 1;
$mu[]=$row;
$mu[]=$col;
break 2;
}
}
}
}
return $mu;
}
-
I appreciate your help and as I feared there is not a simple solution :'( . The league commissioner at this time is creating schedules by hand and it is very tedious. Is comet a web based language or is it a desktop application and do you know if it creates libraries that can be used in web apps?
Thanks
-
I don't think comet comes with any web support, it's a desktop application and I would not expect it to be able to deliver results in real time. I think the only way you could use such a tool in your application would be to create a library of schedules. So an improved algorithm may be your only option.