Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Re: Possible pairings for first knockout round of UEFA champions league

by Anonymous Monk
on Dec 22, 2012 at 14:44 UTC ( [id://1010019]=note: print w/replies, xml ) Need Help??


in reply to Possible pairings for first knockout round of UEFA champions league

Your code seems a bit complicated for a fairly simple task. Label each of the runners up 1-8, generate all 8! permutations, loop through each draw and add 1 to a counter if the permutation of teams does not violate the conditions.
  • Comment on Re: Possible pairings for first knockout round of UEFA champions league

Replies are listed 'Best First'.
Re^2: Possible pairings for first knockout round of UEFA champions league
by LanX (Saint) on Dec 22, 2012 at 15:36 UTC
    It's a branch and bound-algorithm, by early cutting unnecessary branches I avoid calculating all permutations, which is (far¹) more efficient.²

    And it gave me the opportunity to check some mathematical approaches (which are more challenging for me)

    But you're welcome to show us your way to do it!(BTW: I saw your approach already been done in Python, if you're interested)

    Cheers Rolf

    UPDATES:

    ¹) since 8! is only ~40000 it's not too obvious in this special case.

    ²) Furthermore branching allows to cache/memoize results for subtrees to go even faster.

      ²) Furthermore branching allows to cache/memoize results for subtrees to go even faster.
      What? How?
        The algorithm constructs recursively possible combinations of runner-ups meeting an ordered set of group winners:

        Paris Schalke Malaga Dortmund Turin Bayern Barcelona ManU

        now if you take a look at this excerpt of the results and you will notice that the last 4 branches are repeating.

        | ... | Arsenal Porto Donezk Mailand Madrid Celtic Galatasaray Valencia Arsenal Porto Donezk Mailand Valencia Madrid Galatasaray Celtic Arsenal Porto Donezk Mailand Valencia Celtic Galatasaray Madrid Arsenal Porto Donezk Mailand Celtic Madrid Galatasaray Valencia ... | Arsenal Mailand Porto Donezk Madrid Celtic Galatasaray Valencia Arsenal Mailand Porto Donezk Valencia Madrid Galatasaray Celtic Arsenal Mailand Porto Donezk Valencia Celtic Galatasaray Madrid Arsenal Mailand Porto Donezk Celtic Madrid Galatasaray Valencia ... | |

        Which is obviously right since the first 4 are only permutations of the same set.

        So the following pairings (Turin  Bayern   Barcelona  ManU) x (Madrid Celtic Galatasaray Valencia) are always the same.

        Now storing the result for a normalized representation of a already calculated set,

        (something like join "-",sort(@drawn) as a hash key)

        helps reusing the once calculated subresult after encountering any permutation of (Arsenal Mailand Porto Donezk)

        It depends on the ratio between memory and time complexity but this normally gives an enormous boost to such search algorithms.

        Cheers Rolf

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1010019]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others surveying the Monastery: (5)
As of 2024-04-23 23:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found