Page 1 of 2 1 2 LastLast
Results 1 to 10 of 15

Thread: Huge Permutation Problem

  1. #1

    Huge Permutation Problem



    Register for a FREE account, and/
    or Log in to avoid these ads!

    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.
    Last edited by p45cal; 2015-08-13 at 09:45 PM. Reason: removal of non working tags

  2. #2
    Administrator Pecoflyer's Avatar
    Join Date
    Oct 2011
    Location
    Brussels Belgium
    Posts
    1,667
    Articles
    0
    Excel Version
    2010 on Xubuntu
    To say the least , your post is confusing.Perhaps post a sample sheet ?

  3. #3
    Quote Originally Posted by Pecoflyer View Post
    To say the least , your post is confusing.Perhaps post a sample sheet ?
    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.
    Attached Thumbnails Attached Thumbnails Click image for larger version. 

Name:	image.jpg 
Views:	9 
Size:	99.2 KB 
ID:	3843  
    Last edited by p45cal; 2015-08-13 at 09:47 PM. Reason: removal of non-working tags

  4. #4
    Super Moderator p45cal's Avatar
    Join Date
    Dec 2012
    Posts
    1,585
    Articles
    0
    Excel Version
    365
    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.)

  5. #5
    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

  6. #6

  7. #7

  8. #8

  9. #9
    Super Moderator p45cal's Avatar
    Join Date
    Dec 2012
    Posts
    1,585
    Articles
    0
    Excel Version
    365
    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.
    Last edited by p45cal; 2015-08-14 at 02:08 PM.

  10. #10
    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.

Page 1 of 2 1 2 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •