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

Question

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

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?

Answer 1

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.