Combinatorics - UEFA Champions League Draw Algorithm

[crabik]

Homework Statement

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

Homework Equations

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.

 

[haruspex]

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?

 

[crabik]

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.)

This way you may end up in a dead end - 1 spot left but the last team can't be placed there.

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?

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.

 

[Office_Shredder]

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

 

[crabik]

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.

 

[haruspex]

This way you may end up in a dead end - 1 spot left but the last team can't be placed there.

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.)

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.

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?

 

[Julien Guyon]

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)

 

[Ray Vickson]

Homework Statement

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

Homework Equations

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.

Homework Statement

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

Homework Equations

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.

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.