指定された文字列のすべての順列を出力します

特定の文字列のすべての順列を印刷することは、バックトラックの問題の例です。サブ問題を解決するためにサブストリングのサイズを縮小し、次に再びバックトラックしてそのセクションから別の順列を取得します。

たとえば、文字列がABCの場合、すべての順列はABC、ACB、BAC、BCA、CAB、CBAになります。

このアルゴリズムの複雑さはO（n！）です。それは非常に複雑です。文字列のサイズが大きくなると、タスクの完了に時間がかかります。

入力と出力

Input:
A string “ABC”
Output:
All permutations of ABC is:
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]             //for backtrack
      done
End

例

#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]); //swap back for backtracking
      }
   }
}

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