JavaScriptで複数の文字配列から重複文字なしの全組み合わせ文字列を生成する方法

問題の概要

単一文字だけを要素とする配列が n 個あるとします。ここでは、それらの配列をすべて引数として受け取り、条件に合う文字列を生成するJavaScript関数を作成します。

関数が返すべき文字列は、次の2つの条件を満たす必要があります。

• 各配列からちょうど1文字ずつ取り出して構成されていること
• 同じ文字が2回以上登場しないこと(配列同士に共通の文字が含まれる可能性があるため)

本記事では説明のために3つの配列を使用しますが、実装する関数は配列の個数が変わっても正しく動作するよう設計します。

サンプルデータ

const arr1 = ['a', 'b', 'c', 'd'];
const arr2 = ['e', 'f', 'g', 'a'];
const arr3 = ['m', 'n', 'o', 'g', 'k'];

ご覧のとおり、arr2には'a'、arr3には'g'が含まれており、他の配列と重複しています。そのため、「a e a」のように同じ文字が混ざる組み合わせは結果から除外しなければなりません。

実装コード

コードは次のとおりです。

const arr1 = ['a', 'b', 'c', 'd'];
const arr2 = ['e', 'f', 'g', 'a'];
const arr3 = ['m', 'n', 'o', 'g', 'k'];

const allCombinations = (...arrs) => {
    let res = [];
    // ステップ1: すべての配列の直積(全組み合わせ)を生成
    const reduced = arrs.reduce((acc, b) => acc.reduce((r, v) => {
        return r.concat(b.map(el => {
            return [].concat(v, el);
        }));
    }, []));
    // ステップ2: 重複文字を含む組み合わせを除外
    res = reduced.filter(el => new Set(el).size === el.length);
    // ステップ3: スペース区切りの文字列に変換
    return res.map(el => el.join(' '));
};
console.log(allCombinations(arr1, arr2, arr3));

コードの解説

処理は大きく分けて3つのステップで構成されています。

1. 直積(総当たりの組み合わせ)の生成: 外側のreduce()が配列を順番に処理し、内側のreduce()がそれまでに蓄積された各組み合わせに対して、次の配列のすべての文字を連結していきます。こうして1文字→2文字→3文字と組み合わせが育っていきます。引数はレストパラメータ...arrsで受け取っているため、配列が3つでも10個でも同じコードがそのまま使えるのがポイントです。
2. 重複のチェック: new Set(el).size === el.lengthという条件が核心です。Setは重複した値を保持できないため、配列内に同じ文字が含まれていればSetのサイズは元の配列長よりも必ず小さくなります。両者が一致する組み合わせだけがfilter()を通過します。
3. 出力形式への変換: 最後にjoin(' ')を使って、各組み合わせをスペース区切りの読みやすい文字列に整えて返します。

出力結果

コンソールには、重複のない全71通りが出力されます(全配列の素の組み合わせは 4×4×5 = 80通りあり、そのうち9通りが重複を含むため除外されています)。

[
    'a e m', 'a e n', 'a e o', 'a e g', 'a e k',
    'a f m', 'a f n', 'a f o', 'a f g', 'a f k',
    'a g m', 'a g n', 'a g o', 'a g k', 'b e m',
    'b e n', 'b e o', 'b e g', 'b e k', 'b f m',
    'b f n', 'b f o', 'b f g', 'b f k', 'b g m',
    'b g n', 'b g o', 'b g k', 'b a m', 'b a n',
    'b a o', 'b a g', 'b a k', 'c e m', 'c e n',
    'c e o', 'c e g', 'c e k', 'c f m', 'c f n',
    'c f o', 'c f g', 'c f k', 'c g m', 'c g n',
    'c g o', 'c g k', 'c a m', 'c a n', 'c a o',
    'c a g', 'c a k', 'd e m', 'd e n', 'd e o',
    'd e g', 'd e k', 'd f m', 'd f n', 'd f o',
    'd f g', 'd f k', 'd g m', 'd g n', 'd g o',
    'd g k', 'd a m', 'd a n', 'd a o', 'd a g',
    'd a k'
]

補足: パフォーマンスについて

上記のアプローチは簡潔で理解しやすい一方、まずすべての組み合わせを生成してから絞り込むため、配列の数や文字数が増えると組み合わせの総数は指数的に膨れ上がります。入力が大きくなる可能性がある場合は、再帰とバックトラッキングを組み合わせて「重複が判明した時点で枝を切り捨てる」方式を実装すると、無駄な計算を大幅に減らせます。小規模な入力であれば、今回のようなreduce() + Setによる実装で十分に実用的です。