พีชคณิตทั้งหมดของสตริงโดยใช้การวนซ้ำ?

ในส่วนนี้เราจะมาดูวิธีการเปลี่ยนลำดับของสตริงทั้งหมด วิธีการแบบเรียกซ้ำนั้นง่ายมาก ใช้ขั้นตอนการติดตามย้อนกลับ แต่เราจะใช้วิธีวนซ้ำ

การเรียงสับเปลี่ยนทั้งหมดของสตริง 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