ジェネレータで順列と組み合わせを逐次的に生成する – JavaScript

順列は複数の要素を「順番を区別」して選び出したものです。

たとえば 1, 2, 3 の3つの値の順列は、 [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] の6通りとなります。

これをJavaScriptで求めてみます。

順列を生成する

1次元配列の要素から順列を求めます。

function* permutations(data) {
  function* permute(curr, accum = []) {
    if (curr.length === 0) {
      yield accum;
    } else {
      for (let i = 0; i < curr.length; i++) {
        let copy = curr.slice();  //DeepCopy
        let old = copy.splice(i, 1);
        yield* permute(copy.slice(), accum.concat(old));
      }
    }
  }
  yield* permute(data);
}

permutations()関数の引数に順列を生成したい一次元配列を指定します。

実際には関数内のpermute()関数を再帰的に呼び出すことで順列を生成していきます。処理としては以下のような感じです。

① permute([1,2,3]);

② permute([2,3],[1]);

③ permute([3],[1,2]);

④ permute([],[1,2,3]);   => curr.length === 0が成立し”[1,2,3]”を返します。

③ permute([2],[1,3]);

④ permute([[],[1,3,2]);  => [1,3,2]を返します。

同様な処理を再帰的に繰り返していきます。

for-ofでconsole.logから値を確認すると[1,2,3]の配列に対して6通りの順列が生成されることがわかります。

for(let permutation of permutations([1,2,3])){
  console.log(permutation); //[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]
}

順列(nPr)を生成する

次に「n個のうちr個を選んだ時の順列 = nPr」を求められるよう上記のプログラムを修正します。

function* permutations(data,r) {
  const level = data.length - r;  //level = n-r
  function* permute(curr, accum = []) {
    if (level < 0 || curr.length === level) {
      yield accum;
    } else {
      for (let i = 0; i < curr.length; i++) {
        let copy = curr.slice();
        let old = copy.splice(i, 1);
        yield* permute(copy.slice(), accum.concat(old));
      }
    }
  }
  yield* permute(data);
}

“r個”を指定するためにpermutations()に引数rを追加しました。

内部処理としては、変数”level”に”n-r” (nはdata.length)を定義してから再帰処理permute()を実行します。そして、再帰処理で扱う配列currの大きさ(length)がlevelの値に達したら処理を終了させます。

例えば permutations([1,2,3],2)とした場合(3個のうち2個選んだ順列)は、level = 3-2 = 1となり、以下のように処理が実行されます。

① permute([1,2,3]);

② permute([2,3],[1]);

③ permute([3],[1,2]);  => curr.length === 1が成立し”[1,2]”を返します。

③ permute([2],[1,3]);  => “[1,3]”を返します。

② permute([1,3],[2]);

③ permute([3],[2,1]);  => “[2,1]”を返します。

③ permute([1],[2,3]);  => “[2,3]”を返します。

同様な処理を再帰的に繰り返していきます。

for(let permutation  of permutations([1,2,3],2)){
  console.log(permutation); // [1,2],[1,3],[2,1],[2,3],[3,1],[3,2]
}

組み合わせ(nCr)を生成する

組み合わせは複数の要素から「順番を区別せず」に選び出したものです。

たとえば 1, 2, 3 の3つの値を選んだ時の組み合わせは[1,2,3]の1通りとなります。2つ選んだ場合は、[1,2], [1,3], [2,3] の3通りです。

順列(nPr)のプログラムを以下のように修正することで、組み合わせ(nCr)を生成することができます。

function* combinations(data,r) {
  const level = data.length - r;
  function* combinate(curr, accum = [], p = 0) {
    if (level < 0 || curr.length === level) {
      yield accum;
    } else {
      for (let i = p; i < curr.length; i++) {
        let copy = curr.slice();
        let old = copy.splice(i, 1);
        yield* combinate(copy.slice(), accum.concat(old),i);
      }
    }
  }
  yield* combinate(data);
}

関数名をcombinations()に変更しています。

再帰関数もcombinate()に変更していますが、引数”p”を追加しています。この引数pによって重複して値を選び出すことを防ぎます。

例えば combinations([1,2,3],2)とした場合(3個のうち2個選んだ組み合わせ)は、以下のように処理が実行されます。

① combinate([1,2,3]);

② combinate([2,3],[1],0);

③ combinate([3],[1,2],0);  => “[1,2]”を返します。

③ combinate([2],[1,3],1);  => “[1,3]”を返します。

② combinate([1,3],[2],1);

③ combinate([1],[2,3],1);  => “[2,3]”を返します。

② combinate([1,2],[3],2);  => 呼び出しても何も返しません。

結果、[1,2], [1,3], [2,3] の3通りの組み合わせを取得することができます。

for(let combination of combinations([1,2,3],2)){
  console.log(combination); // [1,2], [1,3], [2,3]
}

Related Posts