Tất cả hoán vị của chuỗi dùng vòng lặp

Trong phần này chúng ta sẽ xem cách lấy tất cả hoán vị của một chuỗi. Cách tiếp cận đệ quy rất đơn giản. Nó dùng thủ tục back-tracking. Nhưng ở đây chúng ta sẽ dùng cách tiếp cận lặp.

Tất cả hoán vị của chuỗi ABC là {ABC, ACB, BAC, BCA, CAB, CBA}. Hãy xem thuật toán để hiểu rõ hơn.

Thuật toán

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

Ví dụ

#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);
}

Kết quả

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