JCUnitを支える技術、あるいは再帰もループも用いない順列・組み合わせ列挙のアルゴリズム
今回の話はレポートで組み合わせとか順列の列挙をするプログラムを作る課題をやってる学生さんには面白い話かもしれない。
JCUnitは内部的にcombinatoradix(旧称enumerator)と呼ばれる私が作ったライブラリを使っている。
JCUnitは性質上、かなりヘビーに組み合わせや順列や直積の列挙を行う。そこで、専用の組み合わせ列挙の仕組みを持っている。 もちろん、誰かが作ったライブラリを利用してもいいのだがそうしなかった理由は２つある。
- そもそも外部への依存関係は最小にする必要がある。外部ライブラリを利用すると、そのライブラリ自体のテストにJCUnitが使えなくなるのはもとより、そのライブラリを使用した製品のテストの際にライブラリバージョンによる挙動の違いにより、テスト結果が変化する虞がある。
- 組み合わせを列挙してくれるライブラリは多くあるが、その際に「どのような順番で列挙するか」が明確なものは見つけられなかった。あるかもしれないが、列挙される要素の集合に
a.equals(b)になるような組があった場合の挙動がどうなるか？など不安が多い。
JCUnitの場合、どんな順番で列挙がされるかは非常に重要で、これがないとテストの再現性が損なわれる。
combinatoradixは、「階乗進数」という特殊な記数法を使って、順列の列挙を行う。[1] 5個の要素から3個を選んで並べるとき、そのやり方は5P3=60通りだ。 この時、下からひと桁目は0-4（5進数）、二桁目は0-3(4進数)、三桁目は0-2(3進数)にすると0-234までで60通りの数を表現できる。
| 2nd | 1st | 0th |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| (n/a) | 3 | 3 |
| (n/a) | (n/a) | 4 |
0 1 2 3 4
10 11 12 13 14
20 21 22 23 24
30 31 32 33 34
100 101 102 103 104
110 111 112 113 114
120 121 122 123 124
130 131 132 133 134
200 201 202 203 204
210 211 212 213 214
220 221 222 223 224
230 231 232 233 234
記号[A,B,C,D,E]から3個を取る順列をこの60個の数字に割り当てる。
割り当て方だが、下から順に、その桁の数字に対応する要素を取りさってゆけば良い。例えば。211なら
0th = 1: [A,B,C,D,E] -> "B" (残り:[A,C,D,E])
1st = 1: [A,C,D,E] -> "C" (残り:[A,D,E])
2nd = 2: [A,D,E] -> "E" (残り:[A,D])
つまり[B,C,E]が対応する値となる。
似た様な（しかしもう少し複雑な）記数法を考えると、組み合わせや重複を許す組み合わせについて同じことができる。
この方法は数の計算と要素の対応付けを行うので、可能な組み合わせをすべて列挙するだけなら、再起やループを使ったほうがずっと早いはずだ。 しかし、際立った特徴がある。
例えば「AからZの文字のうち異なる10文字からなる単語を作り、それらを辞書順にならべたときに30億22番目にある単語はなにか？」という問に答えるのは1マイクロ秒くらいでできる。最初からじゅんじゅんにたどっていく必要がないので。 この性質は大量の組み合わせを分散処理や並列処理で高速化して処理したい場合に有効なはずだ。つまり10億通りの組み合わせがあることがわかっていて（100P3とか1000C4とか簡単に公式で求まる）それぞれについて何らかの処理を行いたいのなら、各ノードはその組み合わせの総数（100P3とか1000C4とか）までの数のうち、ノード数で割った余りが自分のノード番号に等しいものだけを処理すればよいのだ。
- [1] 偉そうに書いてしまったが、この方法を考えついたあとに誰かがすでにやってそうなもんだと思い調べてみてこういう名前が付いているの知った。不勉強を恥じる次第
