【C++】指定された文字列のすべての順列を出力するプログラム

この問題では、1つの文字列が与えられます。私たちの課題は、その文字列のすべての順列（パーミュテーション）を出力するC++プログラムを作成することです。

このプログラムは、与えられた文字列から作り得るすべての組み合わせを見つけ出し、それらをすべて出力します。

順列とは、対象を構成するすべての要素を、可能な限りのあらゆる順序で並べた配置のことを指します。

具体例を使って問題を理解してみましょう。

入力

xyz

出力

xyz, xzy, yxz, yzx, zxy, zyx

説明

上記は、順序を変えて並べたすべての順列です。

この問題を解くためには、バックトラッキングという手法を使用します。具体的には、文字列の各文字を順列の先頭の文字として選び、その後、残りの文字を1つずつ順番に選択していくという流れになります。この処理を再帰的に繰り返すことで、文字列のすべての順列を出力することができます。

文字列のすべての順列を出力するプログラム

// 指定された文字列のすべての順列を出力するプログラム −

サンプルコード

#include <iostream>
using namespace std;
void findPermutations(string str, int l, int r){
   if (l == r)
   cout<<str<<" ";
   else{
      for (int i = l; i <= r; i++){
         swap(str[l], str[i]);
         findPermutations(str, l+1, r);
         swap(str[l], str[i]);
      }
   }
}
int main(){
   string str = "WXYZ";
   int n = str.size();
   findPermutations(str, 0, n-1);
   return 0;
}

実行結果

WXYZ WXZY WYXZ WYZX WZYX WZXY XWYZ XWZY XYWZ XYZW XZYW XZWY YXWZ YXZW YWXZ 
YWZX YZWX YZXW ZXYW ZXWY ZYXW ZYWX ZWYX ZWXY

このプログラムでは、関数 findPermutations が再帰的に呼び出され、左端 l の位置にある文字と、それ以降の位置にある各文字を入れ替えながら処理を進めます。左右のインデックスが一致した時点（l == r）で、1つの順列が完成したことになるため、その文字列を出力します。入れ替えた後は元の状態に戻す（スワップを解除する）ことで、次の組み合わせを正しく生成できるようになっています。