Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Round robin tournament problem

by CiceroLove (Monk)
on Oct 21, 2003 at 20:48 UTC ( [id://301061]=perlquestion: print w/replies, xml ) Need Help??

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!'

Replies are listed 'Best First'.
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 edge-colorings of complete graphs. In any case, the solution is certainly not NP-complete, 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 | 7---|----2 8 6----------3 5----4 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 .. $num-2) { print "Round #" . ($partner + 1) . ":\n"; print " $players[-1] vs $players[$partner]\n"; for my $pair (1 .. ($num-2)/2) { my $p1 = ($partner - $pair) % ($num - 1); my $p2 = ($partner + $pair) % ($num - 1); print " $players[$p1] vs $players[$p2]\n"; } }
    Yay combinatorics class!

    blokhead

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.
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 2n players. I have provided working brute-force 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 2n solutions with backtracking is possible.

    Hope this gets you started - L~R

      It is possible just not a ballanced table, you will have a table like the following:
      Round 1 A-B C-D E Sits Out Round 2 B-C D-E A Sits Out ...


      -Waswas
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

Re: Round robin tournament problem
by jsegal (Friar) on Oct 22, 2003 at 19:27 UTC
Re: Round robin tournament problem
by benizi (Hermit) on Oct 22, 2003 at 21:14 UTC

    blokhead's (now-stricken) array above looked awfully like a Latin square to me, and in my search for a Latin square-generating algorithm, I came across Latin Squares, which describes the technique when applied to round-robin scheduling.

    Summary follows the readmore

    Update: To bring this back to perl-land:
    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); }
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

      Here's a function that implements this logic. You pass it the number of players and the round number and it returns a list of numbers. Each pair of numbers is a matchup for that round. (A pair of say 1,4 means "Player 1 plays Player 4".)

      # Function for determining the matchups in a round-robin # 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 > $players-1) { return; } my @list = (1, 1+$round .. $players, 2 .. $round); my @pairs; for (0 .. $#list / 2) { push @pairs, $list[$_], $list[$players-1 - $_]; } 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.

      kelan


      Perl6 Grammar Student

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://301061]
Approved by jdtoronto
Front-paged by broquaint
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others perusing the Monastery: (6)
As of 2024-03-29 15:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found