Huge Permutation Problem

Hello. Please could I have some advice to help solve a problem which has an extraordinary amount of permutations. I feel like I have got lost in the numbers somewhat and could be missing a relatively simple way to solve the problem.
I have a simple sheet that records 100 bets and each bets potential winnings in ROW 2 to ROW 101.
Each bet involves 4 teams, one from each of 4 leagues (entitled League 1, League 2, League 3, League 4).



COL A = team from League 1
COL C = team from League 2
COL E = team from League 3
COL G = team from League 4
COL H = potential winnings for that individual bet.


For a bet to be successful ALL 4 TEAMS MUST WIN. If any of the 4 teams does not win the return from that bet is £0.


There will only be 3 winning teams from League 1,
3 winning teams from League 2,
3 winning teams from League 3,
4 winning teams from League 4.
This makes 13 winning teams in total.


However 12 different teams have been selected from League 1 (giving 12 unique values out of 100 entries),
16 selected from League 2,
15 selected from League 3,
17 selected from League 4.


My question is what combination of 13 teams would give me the maximum return?
Remember only 3 teams will win from Leagues 1,2+3 and 4 teams from League 4.

To say the least , your post is confusing.Perhaps post a sample sheet ?

Pecoflyer said:

To say the least , your post is confusing.Perhaps post a sample sheet ?

Click to expand...

Apologies.

I have four columns (E,G,I,K) containing names of teams.
Next to each team name is a value (columns F,H,J,L).

Column C has the values of F,H,J,L multiplied together and then multiplied by the stake in Column B.

Names of teams can be repeated several times but are always found in the same column. A name in Column E will only ever be found in Column E.

There are maximum of 20 different names of teams in Column E, and a maximum of 24 in Columns G, I and K.

The value assigned to each team name may change from row to row.

Each row is an individual bet. For a bet to be successful all 4 teams on that row must be winners.

At the end of the season only 3 names/teams from Columns E,G,I will be winners and 4 teams from Column K.

The question is which combination of 13 teams winning would give us the highest financial return?

For example would these winners

PREMIERSHIP: Leicester, Watford, Norwich
CHAMPIONSHIP: Derby, Hull, Burnley
LEAGUE 1: Wigan, Barnsley, Swindon
LEAGUE 2: Portsmouth, Luton, Cambridge, Plymouth

be a better financial result for us than these winners

PREMIERSHIP: SUNDERLAND, Watford, Norwich
CHAMPIONSHIP: Derby, Hull, Burnley
LEAGUE 1: Wigan, Barnsley, Swindon
LEAGUE 2: Portsmouth, Luton, Cambridge, Plymouth?

Notice that only one team has changed (Leicester for Sunderland) but because all 4 teams must win for an individual bet to be successful any bet containing Leicester is now worthless.

This one change can affect other teams as well. For example if every time Leicester were picked they were picked with Derby from CHAMPIONSHIP, then all bets containing Derby are also worthless.
Maybe some teams in Leagues 1 and 2 may have their largest potential payouts also relying on Leicester, and maybe some teams that had never been chosen alongside Leicester might be involved in what is now the largest potential payout now Sunderland are winners.

I actually already have a section of the spreadsheet that can work this out manually ie if you type in the names of some teams from each league it will give the potential payout for that particular combination of teams.

The thing is without manually typing in all 1140 possible combinations of 3 teams from PREMIERSHIP which has a maximum of 20 teams, COMBIN(20,3), alongside the 2024 different combinations of 3 teams from CHAMPIONSHIP which has a maximum of 24 teams etc is there a way to find out the list of teams from each league that would give us the highest possible financial payout?

Hope I'm not confusing you! It's harder than I imagined to articulate to somebody what I mean.

LukeClosely, this is a cross post (you have posted the same query elsewhere) without including links to where you have done so.
Please have a careful read of http://www.excelguru.ca/content.php?184 to understand why this important, then make the necessary additions of links to all sites/threads.
Ultimately, LukeClosely, it will be to your benefit.

To others, I would prefer if people considering responding to this thread would delay doing so until LukeClosely has complied.
(LukeClosely has already had plenty of responses at one of his cross posts.)

Apologies for cross posting. I had no idea that different forums were in any way linked by users.

i have also posted this question on MrExcel.com but cannot post a link as I'm not allowed until Iv made 5 posts

4th post

5th post

A plain brute-force technique where every combination of teams is tested would involve many combinations:
Premiership: 3 teams from 20 teams (COMBIN(20,3)) = 1140
Championship: 3 teams from 24 teams (COMBIN(24,3)) = 2024
League 1: 3 teams from 24 teams (COMBIN(24,3)) = 2024
League 2: 4 teams from 24 teams (COMBIN(24,4)) = 10626

You'd have to plug in 1140 * 2024 * 2024 * 10626 team combinations in to that "section of the spreadsheet that can work this out manually". VBA can do this, but the number of combinations is 49,624,446,896,640. I ran a test in vba to time nested loops where the only action at each loop was to increment a value by 1; to run that number of combinations would take the best part of 50 days continuous running. Even if a machine 10 times faster than my oldish machine was used it would still take 5 days. But the action in the middle of a loop would be more than just incrementing a variable. So even if we brought all data into memory (to save the time-consuming process of reading/writing to the sheet) it would not be practical to run.

What remains a mystery and could be useful:
1. "The value assigned to each team name may change from row to row" and "Next to each team name is a value"
How is this value determined/fetched/altered?

2. "a section of the spreadsheet that can work this out manually ie if you type in the names of some teams from each league it will give the potential payout for that particular combination of teams."
It might be good to know how this part of the spreadsheet works so we can duplicate its machinations in vba.

Although as the season progresses teams are being eliminated with a consequent drastic reduction in possible combinations which will, at one point, render the brute-force method practical, my feeling is that there's probably another way; by looking at the 'value assigned to each team' and working forward from that. But we don't know anything about these values so far.

Hello and thank you for taking your time to investigate this.

The values assigned to each team are the odds given by a bookmaker for that particular team to gain promotion from their respective league. As such at the start of the season all teams odds are relatively high as it is obviously tricky to predict which teams will do well. As the season progresses a team doing well will result in their odds shortening and the value assigned to that team will be lower. However a team doing well will be chosen more frequently. A team performing badly will see their odds rise but a teams form will ebb and flow throughout the year. Near the end of the season there will be less and less teams who can realistically challenge for the top places of the league and these teams will have their odds values reduced significantly. Teams chosen regularly will generally have smaller potential winnings but is this preferable to a more surprising result which may have only been chosen once or twice but has much higher payout on each one? Many small winnings better than a few large victories?

The manual section of the sheet simply has an area where team names can be typed in. Then I have added 4 columns next to the other data, one for each league with a formula that will show the value of a team only if the teams named in that row have been typed in the aforementioned area of the sheet. =IF(COUNTIF($F$360:$F$362,E8)>0,F8,0)
There is then a 5th extra column which multiplies these values in the same way as Column C, any team whose name has not been typed in the area has a value of zero so only rows which contain all four teams typed in the area will give a positive result. The sum of this 5th column is the total winnings for that particular combination.

I have also started a section which works in the same way but in reverse. That is to say any team whose name is typed in this second area is eliminated,ie there are further columns working in the same way but in these columns if a teams name has been typed in this team has a value of zero as opposed to the opposite way round.

So when you say:
"The value assigned to each team name may change from row to row."
a team's value will stay the same on a given date.

So 'what combination of 13 teams would give me the maximum return?' might be answered by:
The 3 teams with the longest odds from the Premiership, the 3 teams with the longest odds from the Championship, the 3 teams with the longest odds from League1, the 4 teams with the longest odds from the League2?

No and no

i I can see your logic though

For each bet (each row) we use whichever bookmaker gives the highest payout for all four selections on that bet (row) being correct. Bookmakers may have slightly different odds for the same team. A team may be 2.50 with one bookmaker but 2.70 with another. There is generally more difference between odds the higher the odds for that particular team are. For example a team deemed very likely to succeed will be given very similar odds by all bookmakers so the range may be say 1.66 with the smallest odds given to 1.80 for the highest. But differing bookmakers may offer odds of 20.00 or 34.00 for a long shot. So one bet may use a bookmaker that has a slightly lower value for one team than can be found elsewhere but this is more than compensated for by some of the other teams in the bet having a much higher value than found elsewhere.

Bookmaker A
Leicester 1.80, Derby 2.50, Swindon 5.0, Luton 10.0
gives a combined value of 225

bookmaker B
leicester 1.66, Derby 2.40, Swindon 4.5, Luton 13.0
gives a combined value of 233

notice how the first 3 selections are all smaller but the total value is larger. So on any given date because multiple bets are being placed with multiple bookmakers the value of a team may change on that date, although it will be similar it won't necessarily be the same.

over time a teams value may fluctuate wildly depending on results.

to your second question, it is highly unlikely that anyone would ever choose 4 teams (one from each league) that all had high values because the accumulative chance of this bet winning would be very small. It is much more likely for people to either choose 4 selections with small values because they are deemed more likely to win, or to choose perhaps 3 selections with small to mid values and then one more speculative selection.

If we focussed on purely the teams with the highest values from each league there is a good chance the amount won would be £0, as in no row would you likely find a selection of all 4 large value teams.

Also by purely focussing on the teams that occur most often a team that is deemed almost certain to win will be chosen very regularly but will be chosen with a large variety of other teams meaning a lot of these bets will be losers and the ones that win may have small returns.

The maximum potential win will surely fall somewhere between these 2 camps of a very small number of big winners and a large number of smaller winning bets.

This is is why the combinations are so crucial. A team picked just once with fairly average odds may be found in a large winning bet and therefore may be more valuable overall than a team picked 20 times or a team with much higher odds

The max potential return would be to bet on the 4 teams with the longest odds, at whichever bookmaker gave those long odds. It would also be the least likely to win anything at all.
So you're looking for a balance in between that and going for the 4 teams with the shortest odds which would give you a decent chance of winning, but winning very little.
The bookmakers are quoting odds on each team - the odds vary from team to team depending on how likely they think the teams are going to win. The only way to win something is to be better or luckier at judging the teams than the bookmakers (or looking for mispriced odds). I think you're looking in the wrong direction to find good bet combinations basing your data on the odds that the bookies themselves are giving. You need a separate and good source of information to beat them. I don't even think that if you had a lightening fast computer that could give you the answers of every possible combination in a reasonable time (using the bookies' odds) that it would help in your choice of which bets to place.

The question is not how to pick teams for the bet nor how likely each team is to succeed.

The question is once all bets have been placed which combination of 13 teams winning would give us the highest financial return?

There seems to be some misunderstanding. I'm not asking for any help in choosing which bets to place.

This is is not a betting question. It is purely a spreadsheet question.

Once the sheet has been filled in what combination of names gives the biggest return? I was hoping somebody might have a smart way of narrowing down the search to a number small enough to work out the combinations