JavaScriptで配列内の全要素の組み合わせを取得するアルゴリズム

はじめに

本記事では、文字列の配列を受け取り、その配列に含まれるすべての要素の組み合わせを生成して返すJavaScript関数を作成します。ここでの「組み合わせ」とは、配列から1つ以上の要素を選んで作られるすべてのパターンを指します。

入力例と期待される出力

たとえば、入力配列が次のような場合:

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

出力は次の15通り(空の組み合わせを除いた数)になります。

const output = ["a", "ab", "abc", "abcd", "abd", "ac", "acd", "ad", "b", "bc", "bcd", "bd", "c", "cd", "d"];

アルゴリズムの考え方

この種の問題は再帰(バックトラッキング)を使うと簡潔に実装できます。各インデックスの位置で「その要素を現在の部分組み合わせに追加する」操作を行い、その後続の要素に対して同じ処理を再帰的に繰り返すことで、すべての組み合わせを漏れなく列挙できます。

実装コード

const getCombinations = (arr = []) => {
    const combine = (sub, ind) => {
        let result = [];
        let i, l, p;
        for (i = ind, l = arr.length; i < l; i++) {
            p = sub.slice(0);
            p.push(arr[i]);
            result = result.concat(combine(p, i + 1));
            result.push(p.join(''));
        }
        return result;
    };
    return combine([], 0);
};
console.log(getCombinations(["a", "b", "c", "d"]));

コードのポイント

• combine(sub, ind): これまでに選んだ部分組み合わせ sub と、次に検討する開始インデックス ind を受け取る内部関数です。
• sub.slice(0): 配列をコピーすることで、元の部分組み合わせを汚さずに新しい候補を生成します。
• p.join(''): 選んだ文字列を連結し、1つの組み合わせとして結果に追加します。
• ループの開始位置を i + 1 にすることで、同じ要素の重複選択や順序の重複を防いでいます。

出力結果

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

[
    'abcd', 'abc', 'abd',
    'ab', 'acd', 'ac',
    'ad', 'a', 'bcd',
    'bc', 'bd', 'b',
    'cd', 'c', 'd'
]

まとめ

再帰的なバックトラッキングを用いることで、配列内の要素からすべての組み合わせを簡単に生成できました。ただし、組み合わせの総数は要素数に対して指数関数的に増加するため、要素数が多いデータでは計算量に注意が必要です。