1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics - UEFA Champions League Draw Algorithm

  1. Aug 1, 2013 #1
    1. The problem statement, all variables and given/known data

    I need to create a draw algorithm similar to the UEFA Champions League / Europa League draw.

    Example:

    I have 32 teams, up to 5 teams can be from the same country.

    I need to create:
    A) pairs (round robin style), no 2 teams from the same country can meet
    B) groups of 4 (8 groups each with 4 teams), each team within a group must be from a different country


    2. Relevant equations



    3. The attempt at a solution

    1) Calculate all the possible combinations after each step -> too many combinations.

    2) Use a simple algorithm to make the draw then discard a solution that doesn't meet the criteria and redo the draw -> it's a dirtty solution.
     
  2. jcsd
  3. Aug 1, 2013 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    For B, pick any team at random and assign it to the first group. What other teams are candidates to join the group? (So pick one, etc.)
    For A, I'm not quite clear on the requirement. Does every team have to play every other team that's not from the same country? (That would mean a team from a country with more teams would play fewer matches.) If not, how many matches are to be arranged?
     
  4. Aug 1, 2013 #3
    This way you may end up in a dead end - 1 spot left but the last team can't be placed there.

    Sorry, I ment like playoffs. You take one team and match it up against another. Team A vs Team B, Team C vs Team D, etc. I don't want to end up with the last pair(s) being from the same country, also I don't want to calculate all the possible combinations after picking a pair to find out if it ends up this way 5 picks later. Well it probably wouldn't be too computationally expensive but I want to add couple more conditions to it (like coefficients) which would make it almost impossible.

    It's probably not a trivial question. I'm not sure if this is the right subforum.
     
  5. Aug 1, 2013 #4

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Do you want an algorithm to just make some such seeding, or one that selects a seeding uniformly at random? Because to just make some selection is far easier
     
  6. Aug 1, 2013 #5
    English is not my first language so I'm not sure I understand the question. I want the algorithm to make a random seeding whenever I need it with whatever input data I provide. I may even add some more conditions later (coefficients, etc.). It needs to be somewhat universal.
     
  7. Aug 1, 2013 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    True, but I think there's an easy fix. When starting on a new group, if there are G groups left (including this one) and any country has G unassigned teams, you must pick a team from that country. I think it's clear that the number of such countries cannot exceed the number of teams in a group. This shouldn't distort the odds much, since most of the time you won't run into this. (You could test that by simulation.)
    If you just want one legal pairing up of all teams, that's the same problem but with a group size of 2. But don't you then want further pairings up, this time with the added condition that no two teams should be paired twice?
     
  8. Nov 23, 2014 #7
    Hi Crabik, you might be interested in this: ssrn.com/abstract=2424376
    It gives the answer to your problem (and also guarantees that the random procedure has the uniform distribution, as suggested by Office_shredder)
     
  9. Nov 23, 2014 #8

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper



    Several methods/algorithms are available from the scheduling literature. See, eg.,
    http://en.wikipedia.org/wiki/Round-robin_tournament or
    http://www.mathaware.org/mam/2010/essays/FroncekTournament.pdf .

    This last paper has quite a bit of theory, and constucts graph-theoretic representations to help with the computations.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Combinatorics - UEFA Champions League Draw Algorithm
  1. Combinatorics problem (Replies: 2)

  2. Combinatorics problems (Replies: 8)

  3. Combinatorics question (Replies: 2)

Loading...