JavaScriptで配列内の単語のすべての組み合わせ（順列）を生成する方法

JavaScriptでは、文字列の配列を受け取り、その要素から作り出せるすべての組み合わせ（順列）を生成して返す関数を実装できます。本記事では、再帰呼び出しとバックトラッキングを用いた実装方法を、サンプルコードと実行結果とともにわかりやすく解説します。

実装の考え方

組み合わせの生成には「バックトラッキング」と呼ばれる手法が有効です。各ステップで未使用の要素を1つ選んで現在の文字列に連結し、必要な長さ分だけ再帰的に処理を進めます。残りの長さが0になった時点で、完成した1つの組み合わせを結果配列に格納します。

同じ要素を二重に使わないよう、各要素が使用済みかどうかを記録する真偽値の配列を用意します。配列へのアクセスはO(1)で行えるため、効率的に重複を排除できます。

サンプルコード

const arr = ['a', 'b', 'c', 'd'];
let res = [];

const permutations = (len, val, existing) => {
  // 必要な長さが0になったら、完成した組み合わせを結果に追加
  if (len === 0) {
    res.push(val);
    return;
  }
  for (let i = 0; i < arr.length; i++) {
    // 使用済みフラグで重複を防止（配列参照なのでO(1)）
    if (!existing[i]) {
      existing[i] = true;
      permutations(len - 1, val + arr[i], existing);
      existing[i] = false; // バックトラック：フラグを元に戻す
    }
  }
};

const buildPermutations = () => {
  // 長さ4・3・2・1の順列をそれぞれ生成
  for (let i = 0; i < arr.length; i++) {
    permutations(arr.length - i, '', []);
  }
};

buildPermutations();
console.log(res);

コードのポイント

• permutations関数：引数lenはあといくつ要素を連結するかを示し、valはここまでに構築した文字列、existingは各要素の使用状況を記録します。
• バックトラッキング：再帰から戻った直後にexisting[i]をfalseへ戻すことで、別の分岐で同じ要素を再利用できるようにします。
• buildPermutations関数：長さn・n-1・…・1の順列をすべて網羅できるよう、ループで各長さの生成を開始します。

実行結果

コンソールには、長さ4の順列24個、長さ3の順列24個、長さ2の順列12個、長さ1の並び4個、合計64通りの組み合わせが出力されます。

[
  'abcd', 'abdc', 'acbd', 'acdb', 'adbc', 'adcb',
  'bacd', 'badc', 'bcad', 'bcda', 'bdac', 'bdca',
  'cabd', 'cadb', 'cbad', 'cbda', 'cdab', 'cdba',
  'dabc', 'dacb', 'dbac', 'dbca', 'dcab', 'dcba',
  'abc', 'abd', 'acb', 'acd', 'adb', 'adc',
  'bac', 'bad', 'bca', 'bcd', 'bda', 'bdc',
  'cab', 'cad', 'cba', 'cbd', 'cda', 'cdb',
  'dab', 'dac', 'dba', 'dbc', 'dca', 'dcb',
  'ab', 'ac', 'ad', 'ba', 'bc', 'bd',
  'ca', 'cb', 'cd', 'da', 'db', 'dc',
  'a', 'b', 'c', 'd'
]

計算量の目安

n個の要素からk個を選ぶ順列の総数は n! ÷ (n-k)! で求められます。すべての長さを合わせると組み合わせの総数は要素数の増加に対して急激に膨らむため、この手法は要素数が少ないケース（目安として10個程度まで）に向いています。大量のデータを扱う場合は、ジェネレータを使って必要な分だけ逐次生成するなどの工夫も検討するとよいでしょう。