0. はじめに
前回の記事で森博嗣の「笑わない数学者」における通称「ビリヤードの問題」を一般化した問題について $n \le 17$ まで計算した結果を示した。不思議なことにボールが一個増えるごとに計算時間が綺麗に十倍になり，計算量のオーダーは $O(10^n)$ に見えたが，計算できた範囲が極めて狭かったので $n$ が大きくなると巡回セールスマン問題のように $O(n!)$ のオーダーになる可能性も否定できない。
ということで本問題の計算量オーダーについて考えてみる。
1. 計算量オーダーを考える
とはいったが闇雲に考えても手が出ないので，とりあえず探索空間の広さについて考えてみる。一般化したビリヤードの問題を解くプログラムでは，可能な限りボールの数値の取りうる範囲を狭めることによって探索範囲を限定し，コストの高い重複チェックの回数を減らしている。
それでは，この探索空間の広さはどうなっているのだろうか？探索空間とは，ボールの個数 $n$ としたとき，全てのボールの数値の総和 $\sigma = n(n - 1) + 1$ となり，かつ１と２の玉を必ず含んでいるボールの組み合わせのことだと考える。※ここではボールの配置（順番）は問わない。
手計算で組み合わせ（数）を調べた結果を以下に示す。調べ方はそんなに難しくはない。例えばボールの個数が五個のとき，まず最初の $b_1$ ～ $b_4$ は最小値である１，２，３，４を並べ，残りの $b_5$ は総和が２１になるように１１とする。次に $b_4 < b_5$ が成立する範囲で $b_4$ を一つずつ増やし，$b_5$ は一つずつ減らしていく。これ以上 $b_4$ が増やせなくなると，$b_3$ を一つ増やし，$b_4 = b_3 + 1$ とする。$b_5$ は総和が２１になるように調整し，再度 $b_4 < b_5$ が成立する範囲で $b_4$ を一つずつ増やし，$b_5$ は一つずつ減らしていく。
| ボールの個数 | 総和 | 組み合わせ数 | 組み合わせ |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 3 | 1 | 1 2 |
| 3 | 7 | 1 | 1 2 4 |
| 4 | 13 | 2 | 1 2 3 7 |
| 1 2 4 6 | |||
| 5 | 21 | 7 | 1 2 3 4 11 |
| 1 2 3 5 10 | |||
| 1 2 3 6 9 | |||
| 1 2 3 7 8 | |||
| 1 2 4 5 9 | |||
| 1 2 4 6 8 | |||
| 1 2 5 6 7 |
2. 計算方法
上記の手計算の手続きをプログラムを作成して機械的に求める。
$n$ 個のボールがビリヤードの問題の条件の一部を満たす，すなわち全ボールの数値の合計が $\sigma = n(n -1) + 1$ になる組み合わせの数を考える。組み合わせの数をカウントするだけなので $b_i < b_{i + 1}$ のように整列しているものとする。$b_1 = 1$ かつ $b_2$ として，３番目以降のボールの数値の範囲について考える。
$k$ 番目のボールの数値 $b_k$（$3 \le k < n$）の最小値を $l_k$，最大値を $h_k$ とする。このうち最小値 $l_k$ は前のボールの値 $b_{k - 1}$ を決めた時点で決まっており，$l_k = b_{k - 1} + 1$ となる。
次に $b_k$ の最大値 $h_k$ について考える。$b_k$ より前のボールの数値の総和を $p$ とし，$b_k$ より後のボールの数値の総和を $q$ とする。$p$ は既知であるから，$q$ が最小値を取るときに $b_k$ は最大値 $h_k$ を取る。
\sigma = \underbrace{b_1 + b_2 + \cdots b_{k - 1}}_{p} + b_k + \underbrace{b_{k + 1} + \cdots + b_{n - 1} + b_n}_{q}
$q$ の最小値を考える。各項は前項の値よりも必ず大きいという条件より，全ての項が前項より１だけ大きいときに最小値となる。
\begin{aligned}
q &\ge (h_k + 1) + \cdots + (h_k + n - k) \\
&= (n - k) h_k + \frac{1}{2}(n - k)(n - k + 1)
\end{aligned}
以上より
\begin{aligned}
\sigma &= p + b_k + q \\
&\ge p + (n - k + 1) h_k + \frac{1}{2}(n - k)(n - k + 1)
\end{aligned}
(n - k + 1)h_k \le n(n - 1) + 1 - p - \frac{(n - k)(n - k + 1)}{2}
h_k = \left\lfloor \frac{n(n - 1) + 1 - p}{n - k + 1} - \frac{n - k}{2} \right\rfloor
となる。
こうして $b_k$ の下限値 $l_k$ と上限値 $h_k$ を得られたので，この範囲内で $b_k$ の値を選び，次のボール $b_{k + 1}$ の範囲を順次求めていく。$n$ 個のボールの数値の総和が決まっていることから $b_{n - 1}$ の値を決めると $b_n$ の値も一意に定まる。すなわち $(b_{n - 1}, b_n)$ のペアの取り得る組み合わせは $h_{n - 1} - l_{n - 1} + 1$ 個となる。とくに $k = n - 1$ のとき
h_{n - 1} = \left\lfloor \frac{n(n - 1) - p}{2} \right\rfloor
となり，ペアの組み合わせ数は $h_{n - 1} - l_{n - 1} + 1$ となる。
このようにボールを一個ずつ配置しながら取りうる範囲を限定しつつも最終的な組み合わせ数は最後の２個のときに決まるので，プログラムは再帰的なコードになる。
3. 実装コード
実装コードを以下に示す。今回は C# を用いた。驚いたことに C ネイティブよりも C# のほうが１割ほど速かったのだ。C# すげえな。
using System;
using System.IO;
class COUNT {
static int ball_num; // ボールの個数
static int ball_sum; // ボールの総和
static long count_case( int pos, int sum, int low ) {
int a = ball_sum - sum;
int b = ball_num - pos;
int c = ball_num - pos + 1;
int high = ( 2 * a - b * c ) / ( 2 * c );
long count = 0;
if( pos < ball_num - 2 ) {
for( int i = low; i <= high; i++ )
count += count_case( pos + 1, sum + i, i + 1 );
} else {
for( int i = low; i <= high; i++ )
count += ( ball_sum - sum - i - 1 ) / 2 - i;
}
return( count );
}
static int Main( string[] args ) {
if( args.Length < 1 ) {
Console.Error.WriteLine( "Usage: count(.exe) [ball-num]" );
return( -1 );
}
if( ( ball_num = int.Parse( args[0] ) ) < 5 ) {
Console.Error.WriteLine( "ボールの個数 {0} が不正です!!\n", ball_num );
return( -1 );
}
ball_sum = ball_num * ( ball_num - 1 ) + 1;
long count = count_case( 3, 3, 3 );
Console.Out.WriteLine( "{0}\t{1}", ball_num, count );
return( 0 );
}
}
4. 計算結果
計算結果を以下に示す。なお $n = 25$ のときの計算時間は半日ほどかかった。
| ボールの個数 | 組み合わせ数 | 増加率 |
|---|---|---|
| 1 | 1 | - |
| 2 | 1 | 1.000 |
| 3 | 1 | 1.000 |
| 4 | 2 | 2.000 |
| 5 | 7 | 3.500 |
| 6 | 23 | 3.286 |
| 7 | 84 | 3.652 |
| 8 | 331 | 3.940 |
| 9 | 1,367 | 4.130 |
| 10 | 5,812 | 4.252 |
| 11 | 25,331 | 4.358 |
| 12 | 112,804 | 4.453 |
| 13 | 511,045 | 4.530 |
| 14 | 2,348,042 | 4.595 |
| 15 | 10,919,414 | 4.650 |
| 16 | 51,313,463 | 4.699 |
| 17 | 243,332,340 | 4.742 |
| 18 | 1,163,105,227 | 4.780 |
| 19 | 5,598,774,334 | 4.814 |
| 20 | 27,119,990,519 | 4.844 |
| 21 | 132,107,355,553 | 4.871 |
| 22 | 646,793,104,859 | 4.896 |
| 23 | 3,181,256,110,699 | 4.919 |
| 24 | 15,712,610,146,876 | 4.939 |
| 25 | 77,903,855,239,751 | 4.958 |
計算可能な範囲において，綺麗に $O(5^n)$ の関係を描いているように見える。
ボール数が１個増えるたびに組み合わせ数は増加するが，この増加率が５に漸近しているように見える。
ということで探索空間の広さが $O(5^n)$ であれば，計算量 $O(10^n)$ のアルゴリズムって，まあまあ良く出来ているんじゃないかと思う。
5. 次回
次回に続きます。