JavaScriptで配列の全順列（パーミュテーション）を生成する方法

本記事では、重複のない整数からなる配列が与えられたとき、その配列に含まれる整数のすべての順列（並び替えの組み合わせ）を返すJavaScriptの実装方法を解説します。

問題の概要

例えば、次のような入力配列が与えられたとします。

const arr = [1, 2, 3];

この場合、期待される出力は以下の6通りの順列です。

const output = [
  [1, 2, 3],
  [1, 3, 2],
  [2, 1, 3],
  [2, 3, 1],
  [3, 1, 2],
  [3, 2, 1]
];

実装コード

この問題は、再帰を使ったバックトラッキング（探索の巻き戻し）の考え方で解くことができます。以下がそのコード例です。

const arr = [1, 2, 3];
const findPermutations = (arr = []) => {
    let res = []
    const helper = (arr2) => {
        if (arr2.length == arr.length)
            return res.push(arr2)
        for (let e of arr)
            if (!arr2.includes(e))
                helper([...arr2, e])
    };
    helper([])
    return res;
};
console.log(findPermutations(arr));

実行結果

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

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

コードの仕組み

このアルゴリズムのポイントは以下の通りです。

• helper関数：現在構築中の部分配列 arr2 を受け取り、その長さが元の配列と同じになった時点で、完成した順列として結果 res に追加します。
• 重複チェック：for...of ループで元の配列の各要素を走査し、まだ使用されていない要素のみを新しい配列に追加して再帰呼び出しを行います。
• スプレッド構文 [...arr2, e]：元の配列を破壊せずに新しい配列を生成するため、再帰から戻った際に状態が汚れません。

計算量に関する注意点

要素数 n の配列に対する順列の総数は n!（階乗）で表されます。つまり、配列が大きくなると結果の件数と処理時間が急激に増加します。例えば、5個の要素で120通り、10個の要素では3,628,800通りもの順列が生成されます。実際のアプリケーションで使用する場合は、入力サイズに十分注意してください。