トーナメント

今回は、個人競技や団体競技で用いられるトーナメント対戦表の生成を取り上げます。仮に対戦者数が 12 である場合、一般的には次のようなトーナメント表になります。なお、トーナメント表は ASCII 文字を使って表示しているので、多少見にくいですがご容赦ください。

トーナメント対戦表のプログラムで難しいのは、シード (ここでのシードの意味は単なる１回戦免除) の組み込みです。対戦者数 12 ではシードが A, F, G, L ですが、シード順位は一般的に A, L, F, G の順になります。言い換えると、対戦者数が 15 では A が、14 では A, L が、13 では A, L, F がシードになるということです。

次のプログラムは、コマンドライン引数に 2 から 52 (アルファベット大文字と小文字の合計値) の対戦者数を渡すと、自動的にトーナメント表を作成して表示します。なお、引数を省略すると対戦者数 12 のトーナメント表になります。

 1: use strict;
 2: my $n = $ARGV[0] || 12;          # 対戦者数 (max 52)
 3: my $invol = 2;
 4: $invol *= 2 while $invol < $n;   # 2 の階乗数
 5: my $seed = $invol - $n;          # シード数
 6: my @comb = ('x' x $invol);
 7:
 8: while ($seed--) {                # while ループ内は本文で説明
 9:   if (length($comb[0]) * @comb == $invol) {
10:     $comb[0] =~ s/^xx|xx$/ZZ/;
11:     if ($comb[0] =~ /^ZZx*ZZ$/) {
12:       my $half = length($comb[0]) / 2;
13:       splice @comb, 0, 1, (substr($comb[0], 0, $half), substr($comb[0], $half));
14:     }
15:   } else {
16:     my @target = 0 .. $#comb;
17:     @target = 0 .. ($#target - 1) / 2 while $#target % 2;
18:     my @group_1 = 0 .. $#target / 2;
19:     my @group_2 = ($#target / 2 + 1) .. $#target;
20     splice @comb, $group_2[0], scalar(@group_2), map { scalar(reverse $comb[$_]) } reverse @group_1;
21:   }
22: }
23:
24: foreach my $i (reverse 0 .. $#comb) {   # @comb 配列内の文字列を２文字単位に分解
25:   next if length($comb[$i]) == 2;
26:   my @divide = $comb[$i] =~ /../g;
27:   splice @comb, $i, 1, @divide;
28: }
29:
30: my ($offset, @line) = (0);
31: my @alpha = ('A' .. 'Z', 'a' .. 'z')[0 .. $n - 1];
32: foreach my $i (0 .. $#comb) {           # トーナメント表の下３行の組み立て
33:   if ($comb[$i] eq 'ZZ') {
34:     my $alpha = $alpha[$offset]; $offset++;
35:     $line[2] .= $alpha; $line[1] .= "|"; $line[0] .= "|";
36:   } else {
37:     my $alpha1 = $alpha[$offset]; $offset++;
38:     my $alpha2 = $alpha[$offset]; $offset++;
39:     $line[2] .= "$alpha1 $alpha2"; $line[1] .= "| |"; $line[0] .= " - ";
40:   }
41:   if ($i < $#comb) { $_ .= " "  foreach @line; }
42: }
43:
44: while ($line[0] !~ /^ +\| +$/) {        # トーナメント上部行の作成
45:   my $next = $line[0];
46:   unless ($next =~ s/(-*)-(\1-?)/' ' x length($1) . '|' . ' ' x length($2)/eg) {
47:     $next =~ s/\|( +)\|/' ' . '-' x length($1) . ' '/eg;
48:   }
49:   unshift @line, $next;
50: }
51:
52: s/ +$// foreach @line;         # 末尾の空白を削除
53: print "$_\n" foreach @line;    # トーナメント表の書き出し

Line 24 ～ 27: @comb 配列内の文字列を２文字ずつに分解する

配列内の文字列を分解するのは、トーナメント表の作成を容易にするためです。配列内の各要素は、'ZZ' または 'xx' のどちらかになります。対戦者数 12 を例とすると、分解前と分解後の各要素は次のようになります。

分解前: ZZxx xxZZ ZZxx xxZZ
分解後: ZZ xx xx ZZ ZZ xx xx ZZ

splice @comb, $i, 1, @divide;

配列の各要素を分割するには、splice を使って後ろの要素から順次処理すると比較的うまくいきます。上記のコードで元の１つの要素を複数の要素で置き換えた場合、前から処理すると配列の添字が狂ってループがうまくいきません。

Line 30 ～ 42: トーナメント表の下３行の組み立て

１番下の行は対戦者名であり、@comb 配列の先頭から 'ZZ' には１対戦者名を、'xx' には２対戦者名を左から昇順でアルファベットを割り当てます。下から２行目は、すべて縦線になります。下から３行目は、シードが縦線で、そうでない場合は２対戦者の中間に横線を引きます。

|  -   -  | |  -   -  |
| | | | | | | | | | | |
A B C D E F G H I J K L

Line 44 ～ 50: トーナメント表の上部行の作成

４行目から上部は縦線の行と横線の行が交互に続き、ループで直前行から現在行を生成することができます。３行目から４行目を、４行目から５行目をというふうに進め、縦線１本になったらトーナメント表の作成は終了です。 while ループ内では、２つの正規表現を交互に適用するようになっています。正規表自体は難しいところはないので、解析してみてください。

トーナメントの対戦者数が 2 の累乗になっている場合は、シードを割り当てる必要がないことが知られています。また、2 の累乗のトーナメント表は簡単に作成でき、シード割り当ての出発点とすることができます。例えば、対戦者数が 9 ～ 15 では 16 (2 の 4 乗) のトーナメント表を用意し、17 ～ 31 では 32 (2 の 5 乗) のトーナメント表を用意し、そこから対戦者数になるまでシードを割り当てていくことができます。

シード割り当ての順序は、一見しただけでは規則性がないように見えます。しかし、対称関係にある位置に着目すると、順序付けのヒントを得ることができます。例として、対戦者数 32 から左端のみがシードされているトーナメント表を示しましょう。

極端に小さなトーナメント表は別ですが、それ以外では内部に小さなトーナメント表が含まれます。 32 のトーナメント表では 16 のサイズが２つ、8 のサイズが４つ、4 のサイズが８つ、というような案配です。左端にシードを割り当てたら、それぞれのサイズに対応する１つの対称位置があります。上の表の (1) はトーナメント表全体で、(2) は 1/2 サイズで、(4) は 1/4 サイズで、(8) は 1/8 のサイズでの対称位置を意味します。

シードの割り当ては、左端に無条件に割り当てることから始まります。それ以降は、基本的には左端の対称位置の (1), (2), (4), (8) の順番にシードを割り当てます。ただ、それだけではなく、割り当てられた対称位置も独自の対称位置を持っています。その場合には、対称位置の属するトーナメント表よりも大きなトーナメント表があれば、最上位 (トーナメント表全体) から１つ大きなトーナメント表までの右側にある対称位置にシードを割り当てます。さらに、新しく割り当てられた対称位置も同様の操作をするので、再帰的な処理をすることになります。

d-e(1) はトーナメント表全体の対称位置なので、そこで終わりになります。N-O(2) は 1/2 のサイズの対称位置なので P-Q(1) が、F-G(4) では X-Y(1) と H-I(2) が、B-C(8) では b-c(1) と L-M(2) と D-E(4) が、A の対称位置から派生する対称位置となります。言葉だけではわかりにくいところがあるので、シード割り当ての過程と、順位を加えたトーナメント表を次に示します。なお、最後の T-U にはシードを割り当てることはありません。なぜなら、T-U に割り当てる必要があるなら、最初から 16 のサイズのトーナメント表を用意すればよいことになるからです。

いままでに解説してきたシード割り当てのアルゴリズムを、プログラムのコードとして実装しなければなりません。トーナメント表の順位を観察してみると、2 の１乗までが全体の両端、2 の 2 乗までが 16 のサイズの端、2 の 3 乗までが 8 のサイズの端、残りが 4 のサイズの端であることがわかります。そこで、データ構造として、最初に 2 の累乗数の文字列 ('xxxxxxxx', 'xxxxxxxxxxxxxxxx' 等) を用意して配列 @comb に入れて分割することにしました。文字列の両端がシード割り当ての対象になり、シードを割り当てたら 'xx' を 'ZZ' に変更します。そして、両端とも 'ZZ' になった文字列は、等分の２つの文字列に分割して、分割面に接した 'xx' が後のシード割り当ての対象になります。次の例は、対戦者数 32 ～ 17 までのシード割り当ての様子を示したものです。

ざっと眺めて、どんな感じを受けるでしょうか。後半部分はともかく、31 から 28 あたりの部分は適切にシードが割り当てられている様子を見ることができます。単一だった文字列が分割される過程は、シード割り当ての対象が小さな単位のトーナメント表に移行していくことに対応しています。プログラム中では、２つのケースに分けてシードの割り当てをしています。

シードの割り当てが終了したら、トーナメント表を書き出してプログラムは終了します。プログラムの対戦者数が最大で 52 となっているのは、対戦者名にアルファベットの大文字と小文字を使っているためです。対戦者名を割り当てずに 'X' のように同じ文字を使えば、100 でも 1,000 でもプログラム自体の実行には何の問題もありません。