「再帰 全探索 | アルゴリズムとデータ構造 | Aizu Online Judge」で組み合わせの列挙をする再帰プログラムがあったのでC++で、記事の通り書いてみたけれど、ちょっと動きが分からなかったので修正して、詳細な動きを書いてみました。
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 36 37 38 39 40 41 42 43
|
#include <iostream> #include <string> using namespace std; void printArray(int *S, int n) { for (int i = 0; i < n; i++) { cout << S[i]; if (i != n-1) cout << " "; } cout << endl; } // 組み合わせを列挙 void rec(int i, int *S, int n) { if (i == n) { printArray(S, n); return; } S[i] = 0; rec(i+1, S, n); S[i] = 1; rec(i+1, S, n); } void makeCombination(int *S, int n) { rec(0, S, n); } int main(int argc, char *argv[]) { cin.tie(0); ios::sync_with_stdio(false); int S[3] = { 0 }; makeCombination(S, 3); return 0; } |
AOJのコードの場合は、以下のように、配列がゼロ初期化されていて、rec関数から戻るときにS[i]=1でオン状態になったものは、必ずS[i]=0でオフに戻すという記述のため、※の部分のS[i]の値がぱっと見分からない。
|
void rec(int i, int *S, int n) { if (i == n) { printArray(S, n); return; } // ※ ここのS[i]は? rec(i+1, S, n); S[i] = 1; rec(i+1, S, n); S[i] = 0; // 関数から戻るときにリセット } |
rec関数の最後で、S[i]=0でゼロに戻しているので、基本的には以下と同等です。
|
// 組み合わせを列挙 void rec(int i, int *S, int n) { if (i == n) { printArray(S, n); return; } S[i] = 0; rec(i+1, S, n); S[i] = 1; rec(i+1, S, n); } |
関数の最初でリセットするか呼び出し後の最後でリセットするかの違いです。上記のコードで一度ステップ実行してしまえば理解が深まります。
ステップ実行してみる
要素数が3の組み合わせ一覧をメモ帳で書きながらステップ実行すると、以下のようになります。rec呼び出しでprintしない場合は、必ずS[i]=0となるため上手く動作します。
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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
|
rec(0,S,3)で呼び出し i=0 0==3 S[0]=0 rec(0+1,S,3)で呼び出し i=1 1==3 S[1]=0 rec(1+1,S,3)で呼び出し i=2 2==3 S[2]=0 rec(2+1,S,3)で呼び出し i=3 3==3 printArray(S, n)呼び出し 000出力 return S[2]=1 rec(2+1,S,3)で呼び出し i=3 3==3 printArray(S, n)呼び出し 001出力 return S[1]=1 rec(1+1,S,3)で呼び出し i=2 2==3 S[2]=0 rec(2+1,S,3)で呼び出し i=3 3==3 printArray(S, n)呼び出し 010出力 return S[2]=1 rec(2+1,S,3)で呼び出し i=3 3==3 printArray(S, n)呼び出し 011出力 return S[0]=1 rec(0+1,S,3)で呼び出し i=1 1==3 S[1]=0 rec(1+1,S,3)で呼び出し i=2 2==3 S[2]=0 rec(2+1,S,3)で呼び出し i=3 3==3 printArray(S, n)呼び出し 100出力 return S[2]=1 rec(2+1,S,3)で呼び出し i=3 3==3 printArray(S, n)呼び出し 101出力 return S[1]=1 rec(1+1,S,3)で呼び出し i=2 2==3 S[2]=0 rec(2+1,S,3)で呼び出し i=3 3==3 printArray(S, n)呼び出し 110出力 return S[2]=1 rec(2+1,S,3)で呼び出し i=3 3==3 printArray(S, n)呼び出し 111出力 return |
出力
|
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 |
JavaScriptで実装
|
function rec(i, ary) { if (i == ary.length) { console.log(ary.join(' ')); return; } ary[i] = 0; rec(i+1, ary); ary[i] = 1; rec(i+1, ary); } var A = new Array(3).fill(0); rec(0, A); |
Node.jsで実行
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
|
PS C:\Users\satos_000> node > function rec(i, ary) { ... if (i == ary.length) { ..... console.log(ary.join(' ')); ..... return; ..... } ... ary[i] = 0; ... rec(i+1, ary); ... ary[i] = 1; ... rec(i+1, ary); ... } undefined > > var A = new Array(3).fill(0); undefined > rec(0, A); 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 undefined > |