Fixture List algorithm

mattfoster

Hi,

I need to generate a list of fixtures for a league. I have x number of teams, numbered 1 to x.

Each team must play every other team ONCE, and each team must play no more than once per week.

I thought of an array $match[team1][team2] = $week

Spoken as: $team1 plays $team2 on week $week.

I used the following code to generate a list like:

1 vs 2
1 vs 3
..
1 vs n
2 vs 3
..
2 vs n
3 vs 4
..
3 vs n
..
etc.

But I have no idea how to generate the week numbers for the fixtures, so that no teams play 2ce in one week. Here is my current code.

while ($team1 < ($teamcount - 1)) {
	if ($team2 < $teamcount) {
		if ($team2 > $team1) {
			/* if ((match[$team1][ANYTHING] == $week || match[ANYTHING][$team1] == $week) && (match[$team2][ANYTHING] == $week || match[ANYTHING][$team2] == $week)) {
				$week++;
			   } else {
				$match[$team1][$team2] = $week;
			   }
			*/										
		}
		$team2++;
	} else {
		$team2 = NULL;
		$team1++;
	}
}

Any ideas?

Merve

Set a match variable that holds a week number. If the week is already set on a previous match for that team, set it to the next highest week. This way, each match is a variable that holds a week. It might be a good idea to do this with OOP, but I'm not familiar with it so I'm not the best judge. You can also do this with arrays. You might even want to have a string for each team, for example, the string could start as 1 once one match has been set, then could become 1;2 after setting two matches, then 1;2;3 after setting three matches. Then one can use explode(). Show some more code and I'll be able to help more.

mattfoster

I don't understand your explanation - could you clarify it in PHP for me?

Here's my entire code for the page:

include 'db_conn.php';
mysql_query("Delete from Matches",$link) or die(mysql_error());
$result = mysql_query("Select Count(*) from Teams where TeamActive = 1") or die(mysql_error);
list($teamcount) = mysql_fetch_row($result);
if ($teamcount < 2) {die("Not enough active teams to create fixtures"); }
$teamresult = mysql_query("Select TeamID from Teams where TeamActive = 1",$link) or die(mysql_error());
while ($i < $teamcount) {
	list($teamid[$i]) = mysql_fetch_row($teamresult);
	$i++;
}
$i=NULL;

// $teamno is team number
// $week is week number
// $match[$team1][$team2] = $week
$week = 1;
while ($team1 < ($teamcount - 1)) {
	if ($team2 < $teamcount) {
		if ($team2 > $team1) {
			/* if ((match[$team1][ANYTHING] == $week || match[ANYTHING][$team1] == $week) && 
			(match[$team2][ANYTHING] == $week || match[ANYTHING][$team2] == $week)) {
				$week++;
			   } else {
				$match[$team1][$team2] = $week;
			   }
			*/
			$match[$teamid[$team1]][$teamid[$team2]] = $week;

	}
	$team2++;
} else {
	$team2 = NULL;
	$team1++;
}
}

while (list ($x, $tmp) = each ($match)) {
   while (list ($y, $val) = each ($tmp)) {

echo "$x play $y on week $val <br>";
   }
}

Merve

What I would do is create separate team and match variables. The matches array would hold all the matches. Then each match would either be an array or an object holding the two team numbers, and the week of the match.
Then, for the teams. This is where it gets complex. There is a teams array. Then, each team is an array holding the arrays of which team numbers it has been matched up against and which weeks it is playing in. What one does is checks to see if a week or team is already in the array, then, adds to the array.

As I said, this can also be done with OOP. I'll make some code for this in my spare time, which is limited (damn schoolwork!)

Sorry I can't be of more help.

mattfoster

Cheers, I think I know what you're talking about, I was going to try it before but it looked too heavy!

I want someone to do it for me, or tell me a better way to do it.

I'll sleep on it!

Merve

Do it for you? Fat chance! :p

Yeah, sleeping's good....

I know it seems heavy, but that's the best way I can think of. It'll take a long time to execute the code, so set_time_limit() would be a good function to use. What I would do is something like this:

<?php
set_time_limit(600);
echo "This may take quite a bit of time. Please wait. (Go have a coffee break.)";
ob_start();
//Your code here!
ob_end_flush();
?>

mattfoster

Oh my .. I am a GOD! heheh check this baby:

global $check;
function findweek($teamid1,$teamid2) {
	$tweek = 1;
	while ($t1 != "ok") {
		if (($GLOBALS['check'][$teamid1][$tweek] == "cheese") || ($GLOBALS['check'][$teamid2][$tweek]) == "cheese") {
			$tweek++;
		} else {
			$GLOBALS['check'][$teamid1][$tweek] = "cheese";
			$GLOBALS['check'][$teamid2][$tweek] = "cheese";
			$t1 = "ok";
		}
	}
	return $tweek;
}

while ($team1 < ($teamcount - 1)) {
	if ($team2 < $teamcount) {
		if ($team2 > $team1) {
			$week = findweek($teamid[$team1],$teamid[$team2]);
			$match[$teamid[$team1]][$teamid[$team2]] = $week;										
		}
		$team2++;
	} else {
		$team2 = NULL;
		$team1++;
	}
}

drawmack

Let me get this straight you have 1 to x teams, each team must play each other team 1, each team can only play once per week with no bis.

First let's talk size:
Each team will have x entries in the system, however this is unordered so if team one plays team two then team two played team one.

Okay now this means the following is true:
t1 = x entries
t2 = x-1 entries
.
.
.
tn = x - (n-1) entries
.
.
.
tx = 0 entries

So you're total entries in terms of x is

ary_length = 0;
for(i=1;i<x;i++)
   ary_length = ary_length + x - (i-1);

this reduces to about x² entries in the array.

I seriously hope that x is staying small.

okay now let's talk algorithm:
1) create an array that lists all the teams

<?php
$teams_ary = array();
for($i=0;$i<$x;$i++) {
   $teams_ary[$i] = 'Team ' . $i+1;
}
?>

2) make each team play each other team. Each team can only play once per week.

<?php
$schedule_ary = array()
for($i=0;$i<$x;$i++) {
    $t_one = $teams_ary[$i];
    for($j = $i+1;$j<=$x;$j++) {
        $Week = $i + $j;
        $t_two = $teams_ary[($i+$j)];
        $schedule_ary[(pow(2,$i)+$j] = array(
                 'Week' => $Week,
                 'Team 1' => $t_one,
                 'Teams 2' => $t_two);
    } //end for j
} //end for i
?>

3) figure out how to fix the problem this algorithm has where one game is played in the first week and one game is played in the last week with the graph of the games played per week looking like a cone.

4) figure out how to make this algorithm work of odd numbers of x.

mattfoster

Hi,

My algorithm above works a treat.

Thanks for all the help.

Matt

B_of_W

drawmack;10448626 wrote:
4) figure out how to make this algorithm work of odd numbers of x.

with an odd number of teams one team has no one to play each week so the number of x = x+1 and the last team becomes a phantom meaning anyone playing that team has a week off