CiceroLove has asked for the
wisdom of the Perl Monks concerning the following question:
First off, I would like to point out that I am not a student, this is not a homework assignment and I am really not looking for the code per se but for the methodology and perhaps some gotchyas to programming a round robin tournament. This is for a hobby group I chair. Yes, I know the website runs PHP but this is going to be a tool for tournament directors to help them out.
For the last 3 days, I have stared blankly at my computer screen wondering why this should be so hard. For those of you who may not know what a roudn robin tournament is, if there are 4 players in a tournament each player must play 3 games against the remaining players. The kicker and the point *I think* is tripping me up is that obviously the same player can't play two games with different opponents in the same round. Let's say I have 4 players: A, B, C, D.
This is how the rounds would break down (the # of rounds is always $#players)
Round 1
A vs B
C vs D
Round 2
A vs C
B vs D
Round 3
A vs D
B vs C
Which is easy to program for $#rounds < 6. In fact I got it working quite well. The way I did it was a clever one I thought whereby I just cut the field in half and had the first player play the middle player, second player play the middle player + 1, etc. And then merge the two arrays together then cut it in half and repeat until all rounds were populated. This however will break down in $round >= 6 because the merged array will be the original array and the process starts over again which means that for $players > 7 the players would start playing the same players again. There are no pointers that I could find on the web for round robin tournaments. Plenty for single/double elimination bracket tournaments but round robin seems perhaps to be beyond the scope of normal Japhies.
Help is greatly appreciated.
CiceroLove
Fates! We will know your pleasures: That we shall die, we know; 'Tis but the time, and drawing days out, that men stand upon.  Act III,I, Julius Caesar
20031022 Edit by castaway: Changed title from 'Please Save My Withering Hair!'
Re: Round robin tournament problem
by blokhead (Monsignor) on Oct 22, 2003 at 00:17 UTC

Update 2: The first half of this post was found to be wrong, and lived inside <strike> tags for a long time. Now it's in HTML comments..
Update 2: Wouldn't you know it, in combinatorics class today we actually discussed this exact problem. It has an analogous problem in graph theory dealing with edgecolorings of complete graphs. In any case, the solution is certainly not NPcomplete, and the algorithm is very simple with a visual explanation..
Make a circle out of the competitors, except put one player in the middle. For each round, match up the middle guy with someone, then match up the other ones in a symmetric. It's easier to understand what I mean by "symmetric" with a picture, so here's an example with n=8:
Round 1:
match 8 with 1, then pair up the rest
symmetric to that line..
1

72
8
63
54
Round 2:
match 8 with 2, then pair up the rest
symmetric to the line..
1
7 \ 2
\ \^
\ 8^ \
6 \ 3
\ \
\ \
5 4
Round X: ... keep rotating around the circle, etc
You obviously never get duplicates with the person you put in the middle. But you will also never get duplicates with the other people in the circle, because there are an odd number of them to pair up. You won't get duplicates until you've rotated all the way around.
Doing this in code is pretty easy:
my @players = qw/Frodo Sam Merry Pippin Strider Gandalf Legolas Gimli/
+;
########
my $num = @players;
die "must have even number of players" if $num % 2;
for my $partner (0 .. $num2) {
print "Round #" . ($partner + 1) . ":\n";
print " $players[1] vs $players[$partner]\n";
for my $pair (1 .. ($num2)/2) {
my $p1 = ($partner  $pair) % ($num  1);
my $p2 = ($partner + $pair) % ($num  1);
print " $players[$p1] vs $players[$p2]\n";
}
}
Yay combinatorics class!
 [reply] [d/l] [select] 
Re: Round robin tournament problem
by Grygonos (Chaplain) on Oct 21, 2003 at 20:59 UTC

This isn't the coding that is eluding you.. it's the math. This is a standard combination problem. I think you should look at Dr. Math's Lovely Permutation and Combination FAQ to get handle on what you are trying to do.
Now that you have read that... I think you are trying to do a 4 choose 3 combination. buying a linear algebra or discrete math book may help you here. ... at least that's where I learned about it.
 [reply] 
Re: Round robin tournament problem
by Limbic~Region (Chancellor) on Oct 21, 2003 at 23:40 UTC

CiceroLove,
I only see an easy solution for for 2^{n} players. I have provided working bruteforce code for those cases.
#!/usr/bin/perl w
use strict;
my @name = qw(a b c d e f g h);
die "You must have an even number of players" if @name % 2;
my %tournament;
$tournament{$_} = [] for @name;
for my $round (1 .. $#name) {
$round;
for my $player (@name) {
next if $tournament{$player}>[$round];
for my $opponent (@name) {
next if $opponent eq $player;
next if $tournament{$opponent}>[$round];
next if @{$tournament{$player}} && grep /^$opponent$/ , @{
+$tournament{$player}};
$tournament{$player}>[$round] = $opponent;
$tournament{$opponent}>[$round] = $player;
last;
}
}
}
for my $round (1 .. $#name) {
$round;
print "\n\nRound: $round\n";
my %seen;
for my $player (@name) {
next if $seen{$player};
print "$player plays $tournament{$player}>[$round]\n";
$seen{$tournament{$player}>[$round]} = 1;
}
}
Update: Originally, I stated that this was all that's possible, but as blokhead points out non 2^{n} solutions with backtracking is possible.
Hope this gets you started  L~R  [reply] [d/l] 

It is possible just not a ballanced table, you will have a table like the following:
Round 1
AB
CD
E Sits Out
Round 2
BC
DE
A Sits Out
...
 [reply] [d/l] 
Re: Round robin tournament problem
by dvergin (Monsignor) on Oct 21, 2003 at 23:48 UTC

Update: Drat! I suspect Limbic~Region is right about 2**n. This solution fails for groups of 6 and 10. But for groups numbering in powers of two read on.
Unencumbered as I am by any proper background in such things, let me offer this...
For each round, for each player in succession who does not yet have an opponent in that round, we pick the first available unmatched person who this player has not played in a previous round. For convenience in screening the possibilities, we keep track of the matchings both ways ( A vs B *and* B vs A). and then weed out the dupes later.
You may or may not find this a bit verbose. Season to taste:
#!/usr/bin/perl
use warnings;
use strict;
{
my @round_aoh;
my @players = qw/John Jane Bill Suzi Bret Erin Eric Teri/;
my $rounds = @players  1;
for my $round ( 1..$rounds ) {
for my $player ( @players ) {
next if $round_aoh[$round]{$player};
$round_aoh[$round]{$player} = 'pending';
my ($opponent) = grep {unmatched( $player, $_, \@round_aoh)}
grep {not $round_aoh[$round]{$_}} @players;
$round_aoh[$round]{$player } = $opponent;
$round_aoh[$round]{$opponent} = $player;
}
}
# Now, show what we did.
for my $round ( 1..$rounds ) {
print "Round $round\n";
for my $player ( keys %{$round_aoh[$round]} ) {
# crude hack to skip dupes: A vs B : B vs A
next unless $player gt $round_aoh[$round]{$player};
print " $player vs $round_aoh[$round]{$player}\n";
}
}
}
sub unmatched {
my ($player, $opponent, $round_arefoh) = @_;
for my $round ( 1..@$round_arefoh) {
if (defined $round_arefoh>[$round]{$player}
and $round_arefoh>[$round]{$player} eq $opponent) {
return 0;
}
}
return 1;
}
The rationalle seems right, the code runs, and the results look like they meet the spec. Good luck.
HTH,
David

"Perl is a mess
and that's good because the
problem space is also a mess."  Larry Wall
 [reply] [d/l] 
Re: Round robin tournament problem
by jsegal (Friar) on Oct 22, 2003 at 19:27 UTC

 [reply] 
Re: Round robin tournament problem
by benizi (Hermit) on Oct 22, 2003 at 21:14 UTC

blokhead's (nowstricken) array above looked awfully like a Latin square to me, and in my search for a Latin squaregenerating algorithm, I came across Latin Squares, which describes the technique when applied to roundrobin scheduling.
Summary follows the readmore
Update: To bring this back to perlland:
plays_in_round(player1, player2, N) returns the round, in a tournament of N players, in which player1 plays player2
ex: plays_in_round(5,7,8) == 3
sub plays_in_round {
my ($p1, $p2, $n) = @_;
$n++ if $n % 2;
return undef if $p1 == $p2;
($p1, $p2) = ($p2, $p1) if $p1 > $p2;
$p2 = $p1 if $p2 == $n;
my $r = $p1 + $p2  2;
$r %= $n  1;
$r  ($n  1);
}
 [reply] [d/l] [select] 
Re: Round robin tournament problem
by Anonymous Monk on Oct 22, 2003 at 17:55 UTC

A visually described algorithm:
Look at how A, B and C follow each other
Round 1
D vs A
B vs C
Round 2
D vs C
A vs B
Round 3
D vs B
C vs A
Visualize the diffence between round 1 and 2 as A went where B was, B went where C was and C went where A was. The same replacement holds when you compare round 2 and 3.
Does not this "cylce" method also work with any even number? I think it does. Yea, I think it does.
If so then for any odd number of teams, add a team called "BYE" and you then have an even number of teams. Any team playing the "BYE" team, um, has a bye.
Example: Teams are A,B,C,D,E,F
Round 1
F v A
B v E
C v D
Round 2
F v E
A v D
B v C
Round 3
F v D
E v C
A v B
Round 4
F v C
D v B
E v A
Round 5
F v B
C v A
D v E
Hope that helps.
Zenitram
 [reply] 

# Function for determining the matchups in a roundrobin
# tournament round, given the number of players and the
# round number.
sub matchups {
my $players = shift;
my $round = shift;
# Sanity check the round number
if ($round < 1  $round > $players1) {
return;
}
my @list = (1, 1+$round .. $players, 2 .. $round);
my @pairs;
for (0 .. $#list / 2) {
push @pairs, $list[$_], $list[$players1  $_];
}
return @pairs;
}
If there are an odd number of players, the last pair will be the same number twice (meaning "Player 4 plays Player 4"), which is essentially a bye.
 [reply] [d/l] 

