JavaScriptで文字列のすべての一意な順列（重複なし）を生成する方法

問題

引数として文字列 str を受け取るJavaScript関数を作成します。この関数は、入力文字列から作り出せるすべての順列を生成し、重複が存在する場合はそれらを取り除いて返す必要があります。つまり、入力文字列に含まれる文字を、考えられるあらゆる順序で並べ替えた結果の中から、一意なものだけを求めるということです。

例えば、入力が "aabb" のように同じ文字を含む場合、単純に全並べ替えを行うと同一の文字列が何度も現れますが、本記事の関数では "aabb"、"abab"、"abba" のような一意な組み合わせのみを出力します。

コード例

以下が実際のコードです。

const str = 'aabb';
const permute = (str = '') => {
    if (!!str.length && str.length < 2 ){
        return str
    }
    const arr = [];
    for (let i = 0; i < str.length; i++){
        let char = str[i]
        if (str.indexOf(char) != i)
            continue
            let remainder = str.slice(0, i) + str.slice(i + 1, str.length)
            for (let permutation of permute(remainder)){
                arr.push(char + permutation)
            }
    }
    return arr
}
console.log(permute(str));

出力

上記のコードを実行すると、コンソールには次のように出力されます。

[ 'aabb', 'abab', 'abba', 'baab', 'baba', 'bbaa' ]

コードの仕組み

このアルゴリズムは、再帰的なバックトラッキングの手法を採用しています。処理の流れは以下の通りです。

• ベースケース： 文字列の長さが1以下の場合は、それ以上並べ替えようがないため、そのまま文字列を返します。
• 重複のスキップ： 各位置の文字について、str.indexOf(char) != i が真となる場合（同じ文字がすでにより前の位置で処理済みの場合）は、continue でその反復をスキップします。これにより、同じ文字から始まる順列が重複して生成されることを防いでいます。
• 再帰呼び出し： 現在の文字を除いた残りの部分文字列（remainder）に対して permute() を再帰的に呼び出し、得られた各順列の先頭に現在の文字を連結した結果を配列へ追加していきます。

このように「先頭に置く文字を選ぶ → 残りを再帰的に並べ替える」を繰り返すことで、文字列の長さに関わらず効率的かつ重複のない順列生成を実現できます。