Welcome to the Monastery PerlMonks

### Possible pairings for first knockout round of UEFA champions league

by LanX (Sage)
 on Dec 21, 2012 at 17:16 UTC Need Help??

LanX has asked for the wisdom of the Perl Monks concerning the following question:

The UEFA Champions League is the uber league for European club football¹, combining the best teams of different associations.

Now some conspiracy theories came up after the last drawings for the next round, because an UEFA official predicted the exact pairings at a test screening.

ATM a German news paper tried to calculate the likelihood for this to happen and said that the rules are too complicated for a mathematical approach and a computer program counted 5463 possible pairings

```                                  First knockout round
6.07 The first knock-out round pairings are determined by means of a d
+raw. The
first knockout round is played under the cup (knock-out) system,
+on a home-
and-away basis (two legs). The UEFA administration ensures that t
+he
following principles are respected.
a) Clubs from the same association must not be drawn against each
+ other.
b) The winners and runners-up of the same group must not be drawn
against each other.
c) The group-winners must not be drawn against each other.
d) The runners-up must not be drawn against each other.
e) The runners-up must play the first leg at home.

Now I tried the same, with the following script I counted also 5463 possible pairings.

```#!perl
use strict;
use warnings;

my @first = qw(Paris Schalke Malaga  Dortmund Turin  Bayern   Barcelon
+a  ManU);
my @second= qw(Porto Arsenal Mailand Madrid   Donezk Valencia Celtic
+   Galatasaray);

my @england = qw(ManU Arsenal);
my @italy   = qw(Turin Mailand);
my @spain   = qw(Barcelona Malaga Valencia Madrid);

my @drawn;
my %count_hash;
my \$count;

draw_match();

print \$count,"\n", scalar keys %count_hash;

sub draw_match {

my \$first = \$first[scalar @drawn];

unless ( \$first) {
print "@drawn\n";
\$count++;
\$count_hash{"@drawn"}=1;
return;
}

for my \$second (@second) {
next if \$second ~~ @drawn;
next if not allowed(\$first,\$second);
push @drawn, \$second;
draw_match();
pop @drawn;
}
}

sub allowed {
my (\$first,\$second)=@_;

return if \$second eq \$second[scalar @drawn];             # same grou
+pstage?
return if \$first ~~ @england and \$second ~~ @england;
return if \$first ~~ @italy and \$second ~~ @italy;
return if \$first ~~ @spain and \$second ~~ @spain;

return 1;
}

It's the first time that I used the smart match as an in-operator in arrays, it's not the most efficient way but it clarifies the program logic

I came pretty far with pencil and paper, but the edge cases for teams from the same qualification group take too much effort...

UPDATE:

Anyway I'm not sure that all possible combinations have the same probability to happen...

Cheers Rolf

¹) association football somewhere also known as soccer

Replies are listed 'Best First'.
Re: Possible pairings for first knockout round of UEFA champions league
by Anonymous Monk on Dec 22, 2012 at 14:44 UTC
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.
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

¹) 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?
Re: Possible pairings for first knockout round of UEFA champions league
by jmlynesjr (Deacon) on Dec 22, 2012 at 04:13 UTC

Man U all the way!

James

There's never enough time to do it right, but always enough time to do it over...

All the way to second place :p

Tough first round pairing, but they can take Ronaldo et. al.

James

There's never enough time to do it right, but always enough time to do it over...

> Man U all the way!

Man who?

xD

Cheers Rolf

( addicted to the Perl Programming Language)

Rolf:

Yes, Man U didn't have their act together in Europe this year, at least they won the league title. Looks like an all German final. Should be a good game. I love football regardless of who's playing.

My team is actually the Tampa Bay Rowdies of the 70s and 80s. Lucky to see about 200 games live. Got to see many world-class players like: Marsh, Worthington, Pele, Mueller, Cruyff, Beckenbauer, Granitza. Also saw 6 games of the 94 World Cup in Orlando. It was so hot Dutch fans were passing out in the stands and bags of Gatoraide were being thrown to the players on the field/pitch(:-)) while the game was going on!

James

There's never enough time to do it right, but always enough time to do it over...

Re: Possible pairings for first knockout round of UEFA champions league
by hdb (Monsignor) on May 02, 2013 at 19:08 UTC

Much easier now...

```use strict;
use warnings;
print "Final:  Dortmund vs Bayern\n";

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://1009940]
Approved by Corion
Front-paged by ww
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (6)
As of 2022-05-27 07:16 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Do you prefer to work remotely?

Results (94 votes). Check out past polls.

Notices?