Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re: Round robin tournament problem

by benizi (Hermit)
on Oct 22, 2003 at 21:14 UTC ( #301370=note: print w/replies, xml ) Need Help??


in reply to Round robin tournament problem

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

Only works for EVEN N. For odd N, add 1 and treat the extra player as a bye.

Essentially, you start (step 1:) with an addition chart, mod N-1.

+ 0 1 2 3 4 5 6 0 0 1 2 3 4 5 6 1 1 2 3 4 5 6 0 2 2 3 4 5 6 0 1 3 3 4 5 6 0 1 2 4 4 5 6 0 1 2 3 5 5 6 0 1 2 3 4 6 6 0 1 2 3 4 5

(Step 2:) Copy the diagonal entries to the ends of their columns and the ends of their rows (creating an NxN array)

+ 0 1 2 3 4 5 6 0 *0* 1 2 3 4 5 6 0 1 1 *2* 3 4 5 6 0 2 2 2 3 *4* 5 6 0 1 4 3 3 4 5 *6* 0 1 2 6 4 4 5 6 0 *1* 2 3 1 5 5 6 0 1 2 *3* 4 3 6 6 0 1 2 3 4 *5* 5 7 0 2 4 6 1 3 5

(Step 3:) Relabel the 0's as N-1's, relabel the player numbers, and delete the diagonal.

P 1 2 3 4 5 6 7 8 1 1 2 3 4 5 6 7 2 1 3 4 5 6 7 2 3 2 3 5 6 7 1 4 4 3 4 5 7 1 2 6 5 4 5 6 7 2 3 1 6 5 6 7 1 2 4 3 7 6 7 1 2 3 4 5 8 7 2 4 6 1 3 5

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); }

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://301370]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (8)
As of 2019-10-18 08:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Notices?