使用迭代的字符串的所有排列？

在本节中，我们将看到如何获取字符串的所有排列。递归方法非常简单。它使用回溯过程。但是这里我们将使用迭代方法。

字符串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