Huge Permutation Problem

[LukeClosely]

[COLOR=rgba(0, 0, 0, 0.701961)]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.[/COLOR][COLOR=rgba(0, 0, 0, 0.701961)]
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).
[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]
[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]COL A = team from League 1[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]COL C = team from League 2[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]COL E = team from League 3[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]COL G = team from League 4[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]COL H = potential winnings for that individual bet.[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]
[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]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.[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]
[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]There will only be 3 winning teams from League 1,[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]3 winning teams from League 2,[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]3 winning teams from League 3,[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]4 winning teams from League 4.[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]This makes 13 winning teams in total.[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]
[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]However 12 different teams have been selected from League 1 (giving 12 unique values out of 100 entries),[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]16 selected from League 2,[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]15 selected from League 3,[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]17 selected from League 4.[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]
[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]My question is what combination of 13 teams would give me the maximum return?[/COLOR]
[COLOR=rgba(0, 0, 0, 0.701961)]Remember only 3 teams will win from Leagues 1,2+3 and 4 teams from League 4.

I am happy to answer any questions as without a photo I may not have explained clearly enough.

Thank You[/COLOR]

 

[StephenCrump]

Welcome to the Forum!

It's not clear to me what you're asking here ....

I am only guessing that:

- These 100 bets are the combinations that have been chosen by 100 other people?
- Some teams haven't been picked by anyone, e.g. there are more than 12 teams in League 1, more than 16 in League 2 etc?
- Winnings are based on total bets divided by number of winning entries?

If you can make only one bet under this scenario, and all teams are equally likely to be winners, your best strategy is to pick any combination that hasn't been chosen by others.

In real life of course, some teams are better than others. Your best strategy will involve picking teams that you think the rest of the market has under-rated, and hence picked less frequently than they should have.

The total number of possible bets is not particularly large (160,000 assuming there are 20 teams in each league), but in practice I think you'll only need to compare:

- The probability of each of the 100 bets winning, based on your assessment of each team's odds, and you sharing in the prize pool, and
- Your best bet that is not already in the 100 bets, and you taking 100% of the prize pool.

 

[LukeClosely]

Hello! Thank you for taking the time to reply. Some of your points are very perceptive.

In reality there is a group of us who each place one bet every week and at the end of the season we divide the total prize pot between us equally even if one of us hasn't picked a winner individually as it is a shared effort.

The question I am always asked is "What is the most we could win?". I have a chart on the spreadsheet showing the most valuable individual bets. However this doesn't truly answer the question.

At the end of the season there will be 13 winning teams, 3 in Leagues 1,2,3 and 4 in League 4.

As we have selected 12 teams in League 1 there are actually 220 different ways of grouping 3 different teams from these 12. There are 220 different combinations. For example if the 12 teams were named A-L the combinations are ABC, ABD, ABE, ABF etc.

League 2 there are again 3 winning teams but this time we have selected 16 different teams. The number of different ways you can make 3 out of 16 is even bigger.

So it starts to get complicated. The number of possible outcomes from League 1 AND from League 2 is 220 * however many times you can make 3 out of 16 different teams.

But what I'm after is the best possible outcome.
Which teams from all 4 Leagues would give the best return?
The number of combinations is 220 from League 1 * #League 2 combinations * #League 3 combinations * #League4 combinations.

Hopefully iv explained myself better this time.

 

[StephenCrump]

I agree that if you're choosing 3 teams out of 12, there are 220 combinations = COMBIN(12,3).

But in Post #1 you described the problem as choosing one team from each of Leagues 1, 2, 3 and 4. If League 1 has 20 teams (say) and your syndicate decides that it wants to choose combinations using only those 12 teams (say) it thinks have a realistic chance of winning, then there are only 12 combinations of League 1 teams to play. If it's certain that the three winers will come from these teams, and each has an equal chance, then your probability of success with any pick is 3/12 or 25%, for the League 1 component of the bet.

You say you are placing bets each week, i.e. as the league progresses? How does that work? Surely it's much easier to predict the winners the closer the league is to conclusion, and hence the odds must shorten?

I have a chart on the spreadsheet showing the most valuable individual bets.

How, and by whom, are these values determined?

 

[LukeClosely]

Again thank you for your reply.

The bet works in such a way that at the start of the season it is understandably quite difficult to predict the winners and therefore the odds are much greater but the chance of losing the bet is very high. As the season progresses as you rightly say it becomes easier to predict and the odds shorten considerably but we will have a much higher strike rate of winning bets. So we hope that the fairly regular small winnings towards the end of the season cover the cost of the more speculative bets at the start of the season. The dream of course is to win a couple of the early bets where the returns can be huge. We actually start a week before the season begins and then finish the bet 7-8 weeks before the season ends because by then the odds are so small.

The "most valuable" chart I mentioned simply lists the bets in order of biggest potential payout down to smallest, not by how likely the bets are to win. By definition the larger potential payouts are from the bets least likely to succeed at the time of placement.

I seem to have been a bit unclear about my problem and I apologise for that. Iv tried to simplify and probably made it worse! 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?

For example would these winners

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

be a better financial result for us than these winners

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

Notice that only one team has changed (Leicester for Sunderland) but because all 4 teams must win for 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 League 2, then all bets containing Derby are also worthless.
Maybe some teams in Leagues 3 and 4 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 220 combinations of 3 teams from League 1 alongside all the different combinations of 3 teams from League 2 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.

I would be happy to email you a copy of this years sheet which might give you a better understanding of where I'm coming from.

Thanks again

 

[StephenCrump]

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

Ahhh! Perfectly clear now, thanks.

So if your syndicate chooses combinations using only 12 teams (say) from each league, we'll need to test COMBIN(12,3)^3*COMBIN(12,4) = ~5 billion possibilities. I think this is probably small enough to use brute-force VBA to test all possible combinations.

The number of teams you choose from is likely to increase over the season, but counteracting this, the closer the season is to conclusion, fewer teams have a mathematical chance of finishing in the top 3/4 positions. Typically by the last couple of rounds, there are only 3-6 teams that can finish in the top three, so we'd only need to test these combinations.

I'll aim to post some VBA code for you later in the weekend.

If brute force is impractical because of the number of combinations, there will be smarter ways to approach the problem. For example, I'd probably focus first on the long-shot bets placed at the start of the season. It could be that if one of these comes off it would outweigh the potential winnings from all other bets.

 

[LukeClosely]

Brilliant. Thanks a lot for your help

 

[StephenCrump]

Here’s some code, based on the layout below. The combinations are calculated assuming you’ve numbered your team picks in each league sequentially as 1,2,3 .. N.

I have attached a workbook here: https://app.box.com/s/hbp2c8d6mdfp8ul9pq3i86xaq7z3055m

that tests the relatively simple case where you choose from only five teams from Leagues 1 to 3, and six teams for League 4. The calculation of the optimum winning combination is almost instant. I have also included some checking code that loops inefficiently through all 15,000 combinations to verify the result for you. This might take a minute or so to run.

Unfortunately, brute force can only be used up to a point, because of the potentially huge numbers of combinations. Assuming 100 bets, I found the code reasonably quick for up to 8 teams picked in each league.

If you’re picking from more teams than this, you might need to use some analysis to limit the choices to which you apply brute force.

Excel 2010

	A	B	C	D	E	F	G	H	I	J	K	L
League 1	League 2	League 3	League 4	Best outcome
League 1
League 2
League 3
League 4
Winnings

<tbody>
[TD="align: center"]1[/TD]
[TD="align: center"]Bet #[/TD]

[TD="align: right"]Winnings[/TD]
[TD="align: right"][/TD]

[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]2[/TD]
[TD="align: center"]1[/TD]
[TD="align: center"]1[/TD]
[TD="align: center"]1[/TD]
[TD="align: center"]1[/TD]
[TD="align: center"]1[/TD]
[TD="align: right"]$69[/TD]
[TD="align: right"][/TD]

[TD="align: right"]1[/TD]
[TD="align: right"]2[/TD]
[TD="align: right"]4[/TD]
[TD="align: right"][/TD]

[TD="align: center"]3[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]4[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]3[/TD]
[TD="align: right"]$92[/TD]
[TD="align: right"][/TD]

[TD="align: right"]1[/TD]
[TD="align: right"]3[/TD]
[TD="align: right"]5[/TD]
[TD="align: right"][/TD]

[TD="align: center"]4[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]1[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]5[/TD]
[TD="align: right"]$14[/TD]
[TD="align: right"][/TD]

[TD="align: right"]2[/TD]
[TD="align: right"]4[/TD]
[TD="align: right"]5[/TD]
[TD="align: right"][/TD]

[TD="align: center"]5[/TD]
[TD="align: center"]4[/TD]
[TD="align: center"]5[/TD]
[TD="align: center"]4[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]6[/TD]
[TD="align: right"]$42[/TD]
[TD="align: right"][/TD]

[TD="align: right"]2[/TD]
[TD="align: right"]3[/TD]
[TD="align: right"]5[/TD]
[TD="align: right"]6[/TD]

[TD="align: center"]6[/TD]
[TD="align: center"]5[/TD]
[TD="align: center"]4[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]4[/TD]
[TD="align: center"]4[/TD]
[TD="align: right"]$21[/TD]
[TD="align: right"][/TD]

[TD="align: right"]$334[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]7[/TD]
[TD="align: center"]6[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]4[/TD]
[TD="align: center"]4[/TD]
[TD="align: center"]5[/TD]
[TD="align: right"]$4[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]8[/TD]
[TD="align: center"]7[/TD]
[TD="align: center"]5[/TD]
[TD="align: center"]5[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]4[/TD]
[TD="align: right"]$52[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]9[/TD]
[TD="align: center"]8[/TD]
[TD="align: center"]4[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]5[/TD]
[TD="align: center"]5[/TD]
[TD="align: right"]$59[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]10[/TD]
[TD="align: center"]9[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]3[/TD]
[TD="align: center"]1[/TD]
[TD="align: center"]3[/TD]
[TD="align: right"]$54[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]11[/TD]
[TD="align: center"]10[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]5[/TD]
[TD="align: center"]4[/TD]
[TD="align: center"]6[/TD]
[TD="align: right"]$82[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]12[/TD]
[TD="align: center"]11[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]5[/TD]
[TD="align: center"]5[/TD]
[TD="align: center"]2[/TD]
[TD="align: right"]$25[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]13[/TD]
[TD="align: center"]12[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]1[/TD]
[TD="align: center"]2[/TD]
[TD="align: center"]2[/TD]
[TD="align: right"]$76[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

</tbody>

Test​

Option Explicit
Dim curWinnings() As Currency, curMaxWinnings As Currency
Dim lTeamsChosen() As Long, lCumulativeWinners() As Long
Dim lNoCombinations() As Long, lNoWinners() As Long
Dim lTestCombination() As Long, lBestCombination() As Long
Dim bCombinations() As Boolean
Const NO_OF_LEAGUES = 4
Sub TestBets()

    Dim vBets As Variant
    Dim rngBets As Range
    Dim lNoTeamsChosen() As Long, lTotalNoWinners As Long, i As Long, j As Long, k As Long
    Dim lCombinations() As Long, lMaxCombinations As Long, lNoBets As Long
    Dim lMaxTeams As Long, lMaxWinners As Long, lCount As Long
    Dim vResults() As Variant
    ReDim lNoWinners(1 To NO_OF_LEAGUES)
    ReDim lCumulativeWinners(1 To NO_OF_LEAGUES)
    ReDim lNoTeamsChosen(1 To NO_OF_LEAGUES)
    ReDim lNoCombinations(1 To NO_OF_LEAGUES)
    
    lNoWinners(1) = 3
    lNoWinners(2) = 3
    lNoWinners(3) = 3
    lNoWinners(4) = 4
        
    'Load bets
    Set rngBets = Range("B2:B" & Range("B" & Rows.Count).End(xlUp).Row).Resize(, NO_OF_LEAGUES + 1)
    vBets = rngBets.Value
    lNoBets = UBound(vBets)
    ReDim lTeamsChosen(1 To lNoBets, 1 To NO_OF_LEAGUES)
    ReDim curWinnings(1 To lNoBets)
    For i = 1 To lNoBets
        For j = 1 To UBound(vBets, 2) - 1
            lTeamsChosen(i, j) = vBets(i, j)
        Next j
        curWinnings(i) = vBets(i, UBound(vBets, 2))
    Next i
    
    'Initialise
    For i = 1 To NO_OF_LEAGUES
        lNoTeamsChosen(i) = WorksheetFunction.Max(rngBets.Columns(i))
        lTotalNoWinners = lTotalNoWinners + lNoWinners(i)
        lCumulativeWinners(i) = lTotalNoWinners - lNoWinners(i)
        lMaxTeams = WorksheetFunction.Max(lMaxTeams, lNoTeamsChosen(i))
        lMaxWinners = WorksheetFunction.Max(lMaxWinners, lNoWinners(i))
        lNoCombinations(i) = WorksheetFunction.Combin(lNoTeamsChosen(i), lNoWinners(i))
        lMaxCombinations = WorksheetFunction.Max(lMaxCombinations, lNoCombinations(i))
    Next i
    ReDim bCombinations(1 To NO_OF_LEAGUES, 1 To lMaxCombinations, 1 To lMaxTeams)
    ReDim lTestCombination(1 To NO_OF_LEAGUES)
    ReDim vResults(1 To NO_OF_LEAGUES + 1, 1 To lMaxWinners)
       
    'Generate combinations, and convert to expanded Boolean array for easier checking against bets placed
    For i = 1 To NO_OF_LEAGUES
        lCombinations = GetCombinations(lNoTeamsChosen(i), lNoWinners(i))
        For j = 1 To lNoCombinations(i)
            For k = 1 To lNoWinners(i)
                bCombinations(i, j, lCombinations(j, k)) = True
            Next k
        Next j
    Next i
    
    'Test bets (recursive to accommodate variable no of leagues)
    Call TestCombinations(1)
    
    'Post results
    For i = 1 To NO_OF_LEAGUES
        lCount = 0
        For j = 1 To lMaxTeams
            If bCombinations(i, lBestCombination(i), j) Then
                lCount = lCount + 1
                vResults(i, lCount) = j
            End If
        Next j
    Next i
    vResults(i, 1) = curMaxWinnings
    Range("I2").Resize(NO_OF_LEAGUES + 1, lMaxWinners).Value = vResults
    
End Sub
Sub CalculateWinnings()

    Dim i As Long, j As Long
    Dim curTotalWinnings As Currency
    
    For i = 1 To UBound(lTeamsChosen)
        For j = 1 To NO_OF_LEAGUES
            If Not bCombinations(j, lTestCombination(j), lTeamsChosen(i, j)) Then Exit For
        Next j
        If j > NO_OF_LEAGUES Then curTotalWinnings = curTotalWinnings + curWinnings(i)
    Next i
    If curTotalWinnings > curMaxWinnings Then
        curMaxWinnings = curTotalWinnings
        lBestCombination = lTestCombination
    End If

End Sub
Sub TestCombinations(lLeague As Long)

    Dim i As Long
        
    For i = 1 To lNoCombinations(lLeague)
        lTestCombination(lLeague) = i
        If lLeague = NO_OF_LEAGUES Then
            Call CalculateWinnings
        Else
            Call TestCombinations(lLeague + 1)
        End If
    Next i
        
End Sub
Function GetCombinations(lNumber As Long, lNoChosen As Long) As Long()

    Dim lOutput() As Long, lCombinations As Long
    Dim i As Long, j As Long, k As Long
    
    lCombinations = WorksheetFunction.Combin(lNumber, lNoChosen)
    ReDim lOutput(1 To lCombinations, 1 To lNoChosen)
    
    For i = 1 To lNoChosen
        lOutput(1, i) = i
    Next i
    
    For i = 2 To lCombinations
        For j = 1 To lNoChosen
            lOutput(i, j) = lOutput(i - 1, j)
        Next j
        For j = lNoChosen To 1 Step -1
            lOutput(i, j) = lOutput(i, j) + 1
            If lOutput(i, j) <= lNumber - (lNoChosen - j) Then Exit For
        Next j
        For k = j + 1 To lNoChosen
            lOutput(i, k) = lOutput(i, k - 1) + 1
        Next k
    Next i
    
    GetCombinations = lOutput
    
End Function

 

[LukeClosely]

That's terrific thanks for your time and effort. As the season goes on some teams picked early on can be eliminated anyway so hopefully this will keep the number manageable. Thanks again. Great stuff!

 

[LukeClosely]

Had an idea how to reduce the number of teams used for these calculations. I have made an area on the spreadsheet where teams can be manually ruled out as the season goes along by typing their name into a box and there are columns which calculate the individual bet winnings when these teams are given a value of 0. This way all bets containing any of these ruled out teams give a return of 0.

I've then written a list of every team in each league and using these new columns and the SUMIF function totalled the winnings for each individual team. The 5 teams with the largest values for each league (6 in league 4) can then be used.