【JavaScript】整数配列から可能なすべての順列を生成する関数の実装方法

本記事では、整数の配列を引数として受け取り、その要素を使って作成できるすべての順列(並べ替え)を配列として返す関数を、JavaScriptで実装する方法を解説します。

実装する関数の仕様

• 整数の配列を引数として受け取る(例:[1, 2, 3, 4])
• 元の配列と同じ長さ(この例では4要素)の順列をすべて生成する
• 生成したすべての順列を格納した配列を返す

アルゴリズムの考え方(バックトラッキング)

ここでは「バックトラッキング」と呼ばれる手法を使用します。処理の流れは以下の通りです。

1. 配列から要素を1つ取り出し、使用済みの要素を保持する配列(used)に追加する
2. 元の配列が空になったら、usedのコピーを結果配列(res)にpushする
3. 残りの要素に対して再帰的に同じ処理を繰り返す
4. 再帰から戻ったら、取り出した要素を配列の元の位置へ戻し(バックトラック)、usedからも削除する

この「選択 → 探索 → 解除」のサイクルを繰り返すことで、重複なくすべての並べ方を網羅できます。

コード例

const arr = [1, 2, 3, 4];
const permute = (arr = [], res = [], used = []) => {
   let i, ch;
   for (i = 0; i < arr.length; i++) {
      ch = arr.splice(i, 1)[0];
      used.push(ch);
      if (arr.length === 0) {
         res.push(used.slice());
      }
      permute(arr, res, used);
      arr.splice(i, 0, ch);
      used.pop();
   };
   return res;
};
console.log(permute(arr));

実行結果

コンソールには次のように出力されます。

[
   [ 1, 2, 3, 4 ], [ 1, 2, 4, 3 ],
   [ 1, 3, 2, 4 ], [ 1, 3, 4, 2 ],
   [ 1, 4, 2, 3 ], [ 1, 4, 3, 2 ],
   [ 2, 1, 3, 4 ], [ 2, 1, 4, 3 ],
   [ 2, 3, 1, 4 ], [ 2, 3, 4, 1 ],
   [ 2, 4, 1, 3 ], [ 2, 4, 3, 1 ],
   [ 3, 1, 2, 4 ], [ 3, 1, 4, 2 ],
   [ 3, 2, 1, 4 ], [ 3, 2, 4, 1 ],
   [ 3, 4, 1, 2 ], [ 3, 4, 2, 1 ],
   [ 4, 1, 2, 3 ], [ 4, 1, 3, 2 ],
   [ 4, 2, 1, 3 ], [ 4, 2, 3, 1 ],
   [ 4, 3, 1, 2 ], [ 4, 3, 2, 1 ]
]

計算量に関する注意点

n個の要素の順列は全部で n!(階乗)通り存在するため、このアルゴリズムの時間計算量は O(n!) となります。要素数が増えると組み合わせの総数が爆発的に増加するため、実用上は要素数が比較的少ないケース(目安として10個程度まで)に適した手法です。