Algorithm to determine the highest and lowest possible finishing position of a team in a league

12
votes

Not sure if this is an appropriate question for SO, but here goes:

I am interested in the required logic needed to be able to calculate the highest and lowest possible finishing position of a team in a league.

Take for example the English Premier League. There are 20 teams in this league. Each team hosts every other team in the league once at home. This means that each team plays each other twice (once at home and once away), and so will play 38 games in a season.

A game can end in one of three results- a home win, a draw, or an away win. Teams are awarded 3 points for a win, and one point for a draw. This means that the maximum amount of points a team can achieve in a single season is 114 (38*3).

The bottom of this year's Premier League table currently looks like this (Position, Team name, Games played, Goal difference [goals scored - goals conceded], Points) :

Premier League as at 14/5/13

I want to know Newcastle's highest and lowest possible finishing positions.

It would be rational to think that Newcastle's lowest finishing position this season would be 18th, as if Newcastle lose their remaining game, and all the teams below them (with the exception of QPR and Reading who can't catch Newcastle) win their games, then their points total will be higher than Newcastle's (Wigan's will be the same, but the fact that they will have had two wins, and Newcastle will have had one loss will mean that Wigan will have a superior Goal Difference [the mechanism to separate teams who are on equal points]).

However- (and this is the complicated bit)- Aston Villa's final game of the season is against Wigan. For this reason, it is impossible for both teams to gain maximum points.

So my question is- which is the best way to accurately determine the highest and lowest possible finishing place of a given team in a league, whilst taking into account the remaining fixtures of rival teams? Should I just look at every remaining fixture and calculate each permutation? Or is there a smarter way to do this?

1
algorithmlanguage-agnostic
For just one round brute force should handle it nicely, since there are only 3^10 possible outcomes. It is easy to see however that it will quickly get out of hand if you try to do it for more rounds. – amit
Yes one round is simple enough, I was wondering if there was a smarter way to do it however. – Chris Payne
Actually, there are slightly less possible outcomes, as if we want to know Newcastle's highest or lowest position, then we should always give them a win or a loss respectively – Chris Payne
Yea, It is indeed interesting! (upvoted). my intuition goes with dynamic programming, but cannot see how yet. Will try to give it some more thought later on today if no good answer will pop up. – amit
The "baseball elimination problem" may be of some help, it's a reasonably well-studied problem. It uses the maximum flow algorithm. Example. Not sure whether you can apply it to determine min and max positions, you'll have to check. – Bernhard Barker

1 Answers

4
votes

You can reduce the number of combination by ignoring the irrelevant ones.

The steps below are for finding the lowest possible position. Finding the highest possible position would be handled in a similar way.

When considering the lowest possible position, the teams that are ahead are irrelevant.

Also teams that cannot get enough points to reach Newcastle in the remaining games are irrelevant.

For the remaining teams, consider each game against an irrelevant team as won.

The above step can make more teams irrelevant. If so, repeat the previous step!

Brute-force the remaining games, i.e. games where relevant teams face each other.