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);
}
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.