再帰: 値の組み合わせを求める-アルゴリズム入門

スポンサーリンク

問題: (0, 1) の組み合わせを求める

要素数が3つの配列

var arr = [0, 0, 0];

この配列に対して0か1の値を代入し、 すべての組み合わせを求めます。

結果として次のような出力ができるようにします。

Array [ 0, 0, 0 ]
Array [ 0, 0, 1 ]
Array [ 0, 1, 0 ]
Array [ 0, 1, 1 ]
Array [ 1, 0, 0 ]
Array [ 1, 0, 1 ]
Array [ 1, 1, 0 ]
Array [ 1, 1, 1 ]

コードは次の通りです

function f(n, max){

    var i = 0;

    if (n >= max){
        console.log(arr);
        return true;
    }else{

        arr[n] = 0;      // 0 を代入
        f(n + 1, max);

        arr[n] = 1;      // 1 代入
        f(n + 1, max);
    }

}

var arr = [0, 0, 0];

var len = arr.length;    // 配列の要素数を取得

f(0, len);

var arr = [0, 0, 0]; の部分を変更すれば要素数が何個でもできます。

問題: (0, 1, 2) の組み合わせを求める

配列の要素数を2にして、(0, 1, 2) の組み合わせを求めてみます。

出力結果

Array [ 0, 0 ]
Array [ 0, 1 ]
Array [ 0, 2 ]
Array [ 1, 0 ]
Array [ 1, 1 ]
Array [ 1, 2 ]
Array [ 2, 0 ]
Array [ 2, 1 ]
Array [ 2, 2 ]

前回のソースに追加する形で次のように記述してもいいのですが、

        arr[n] = 0;      // 0 を代入
        f(n + 1, max);

        arr[n] = 1;      // 1 代入
        f(n + 1, max);

        arr[n] = 2;      // 2 代入 (2行を追加記述)
        f(n + 1, max);

さらに組み合わせのパターンが増えても対応できるようにします。

ここではシンプルにfor文をつかって記述します。他の方法でももちろんかまいません。 コードは次の通りです。

function f(n, max){

    var i = 0;

    if (n >= max){
        console.log(arr);
        return true;
    }else{

        for (i = 0; i < arr_flg.length; i++){
            arr[n] = arr_flg[i];
            f(n + 1, max);
        }
    }
}

var arr = [0, 0];

var arr_flg = [0, 1, 2];    // とりうる値を記述

var len = arr.length;  // 配列の要素数を取得

f(0, len);

問題: 配列を動的に変更する

次は、配列 arrの最大要素数を3とし、動的に配列の要素数を変更していきます。 とりうる値は(0, 1)とします。

出力結果を見て、配列の要素数が増えたり、減ったりしているのを確認してください。

出力結果

Array [ 0 ]
Array [ 0, 0 ]
Array [ 0, 0, 0 ]
Array [ 0, 0, 1 ]
Array [ 0, 1 ]
Array [ 0, 1, 0 ]
Array [ 0, 1, 1 ]
Array [ 1 ]
Array [ 1, 0 ]
Array [ 1, 0, 0 ]
Array [ 1, 0, 1 ]
Array [ 1, 1 ]
Array [ 1, 1, 0 ]
Array [ 1, 1, 1 ]

コードは次の通りです。

function f(n, max){

    var i = 0;

    if (n >= max){
        return true;
    }else{

        for (i = 0; i < arr_flg.length; i++){

            arr.length = n;      // 配列の要素数を変更

            arr[n] = arr_flg[i];
            console.log(arr);    // 出力
            f(n + 1, max);
        }
    }

}

var arr = [];

var arr_flg = [0, 1];    // とりうる値を記述

var len_max = 3;  // 配列の最大要素数

f(0, len_max);