【C++】指定した文字列の全順列を出力する方法（バックトラッキングで解説）

はじめに

指定された文字列のすべての順列（並べ替えの組み合わせ）を出力する問題は、バックトラッキングを用いるアルゴリズムの代表的な例です。基本的な考え方は、対象となる部分文字列の範囲を少しずつ狭めながら部分問題を解決していき、処理が終わったら状態を元に戻す（バックトラックする）ことで、同じ区間から別の順列を次々と生成するというものです。

たとえば、文字列が「ABC」の場合、すべての順列は以下の6通りになります。

• ABC
• ACB
• BAC
• BCA
• CAB
• CBA

このアルゴリズムの計算量は O(n!) と非常に大きくなります。文字列の長さが増えるにつれて、必要な処理時間は爆発的に増加するため、短い文字列向けの手法である点に注意が必要です。

入力と出力

Input:
文字列 "ABC"
Output:
ABC のすべての順列:
ABC
ACB
BAC
BCA
CBA
CAB

アルゴリズム

stringPermutation(str, left, right)

入力： 対象の文字列と、操作範囲を示す左端・右端のインデックス。

出力： 文字列のすべての順列を表示します。

Begin
    if left = right, then
        display str
    else
        for i := left to right, do
            swap str[left] and str[i]
            stringPermutation(str, left+1, right)
            swap str[left] and str[i]   // バックトラッキング用に元へ戻す
        done
End

動作のポイント

このアルゴリズムでは、現在位置 left の文字と、それ以降の各位置 i の文字を順番に入れ替えます。入れ替えるごとに再帰呼び出しを行い、left と right が一致した時点で1つの順列が完成します。再帰から戻る際にもう一度入れ替えを行って文字列を元の状態に復元することで、次の組み合わせを正しく試せるのがバックトラッキングの重要なポイントです。

C++による実装例

#include<iostream>
using namespace std;

void stringPermutation(string str, int left, int right) {
    if(left == right)
        cout << str << endl;
    else {
        for(int i = left; i<= right; i++) {
            swap(str[left], str[i]);
            stringPermutation(str, left + 1, right);
            swap(str[left], str[i]); // バックトラッキングのため元に戻す
        }
    }
}

int main() {
    string str = "ABC";
    cout << "All permutations of " << str << " is: " <<endl<<endl;
    stringPermutation(str, 0, str.size()-1);
}

実行結果

All permutations of ABC is:
ABC
ACB
BAC
BCA
CBA
CAB

まとめ

文字列の全順列の生成は、再帰とバックトラッキングを組み合わせたシンプルかつ強力なテクニックです。「入れ替え → 再帰 → 元に戻す」という流れを理解すれば、Nクイーン問題や組み合わせ探索など、他の多くのバックトラッキング問題にも応用できます。ただし計算量が O(n!) であるため、扱う文字列の長さには十分注意しましょう。