やった。これはAOJのALDS1_5_Aのための組み合わせ列挙を再帰関数でやるというもの。

少し前から少しづつAOJをやっているのはこの記事の参考として後ろの方に載せている「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」をやり始めたからというのがある。

んで、その本の中の「6.2: 全探索」でALDS1_5_Aを解くために再帰関数で組み合わせ列挙の解説があるが、疑似コードを読んでも全く理解できず、頭が痛くなったので数日ほったらかしていた。やらないと進まないので重い腰を上げて取り組んだ。

コード


実際に書いてデバッグしてようやく理解できた。文章だと説明し辛いが、例えば$2^3 = 8$通りの組み合わせの場合、深さ3でリーフノード数が8の二分木を順にたどるイメージ。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function generateCombination(e) {
let S = [];
for (i = 0; e > i; i++) {
S.push(0);
}
select(0, e, S)
}

function select(i, e, S) {
if (i === e) {
console.log(S);
return;
}

select(i + 1, e, S);
S[i] = 1;
select(i + 1, e, S);
S[i] = 0;
}

generateCombination(3);

/*
以下実行結果

node generateCombination.js
[ 0, 0, 0 ]
[ 0, 0, 1 ]
[ 0, 1, 0 ]
[ 0, 1, 1 ]
[ 1, 0, 0 ]
[ 1, 0, 1 ]
[ 1, 1, 0 ]
[ 1, 1, 1 ]
*/

所感


なんとか理解できたものの、こういうのに当たるたびに心が折れそうになってしまう。そんで、毎日心が折れそうになってるので毎日この職業をやめたいと思ってしまう。しかし、折れたところでやらないと進まないので一つずつやっていくしかない…。人生がKIBISHII…

参考


プログラミングコンテスト攻略のためのアルゴリズムとデータ構造