ในส่วนนี้เราจะดูวิธาหาการเรียงสับเปลี่ยน (permutations) ทั้งหมดของสตริง วิธี Recursive ใช้ Backtracking ง่าย แต่ที่นี่ใช้วิธี Iterative
Permutations ของ "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 from i to end.
done
end
ตัวอย่างโค้ด (C++)
#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
