反復を使用した文字列のすべての順列？

このセクションでは、文字列のすべての順列を取得する方法を説明します。再帰的アプローチは非常に単純です。バックトラッキング手順を使用します。ただし、ここでは反復アプローチを使用します。

文字列ABCのすべての順列は、{ABC、ACB、BAC、BCA、CAB、CBA}のようなものです。より良いアイデアを得るためのアルゴリズムを見てみましょう。

アルゴリズム

getAllPerm（str）

begin
   sort the characters of the string
   while true, do
      print the string str
      i := length of str – 1
      while str[i - 1] >= str[i], do
         i := i – 1
         if i is 0, then
            return
         end if
      done
      j := length of str – 1
      while j > i AND str[j] <= str[i – 1], do
         j := j – 1
      done
      exchange the characters from position str[i - 1], str[j]
      reverse the string.
   done
end

例

#include <iostream>
#include <algorithm>
using namespace std;
void getAllPerm(string str){
   sort(str.begin(), str.end());
   while (true){
      cout << str << endl;
      int i = str.length() - 1;
      while (str[i-1] >= str[i]){
         if (--i == 0)
         return;
      }
      int j = str.length() - 1;
      while (j > i && str[j] <= str[i - 1])
      j--;
      swap(str[i - 1], str[j]);
      reverse (str.begin() + i, str.end());
   }
}
int main(){
   string str = "WXYZ";
   getAllPerm(str);
}

出力

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