In tất cả các hoán vị của một chuỗi đã cho là một ví dụ về bài toán bẻ khóa ngược. Chúng tôi sẽ giảm kích thước của chuỗi con để giải quyết các vấn đề con, sau đó quay lại một lần nữa để lấy một hoán vị khác từ phần đó.
Ví dụ:nếu chuỗi là ABC, tất cả các hoán vị sẽ là ABC, ACB, BAC, BCA, CAB, CBA.
Độ phức tạp của thuật toán này là O (n!). Đó là một sự phức tạp rất lớn. Khi kích thước chuỗi tăng lên, sẽ mất nhiều thời gian hơn để hoàn thành tác vụ.
Đầu vào và Đầu ra
Input: A string “ABC” Output: All permutations of ABC is: ABC ACB BAC BCA CBA CAB
Thuật toán
stringPermutation(str, left, right)
Đầu vào: Chuỗi và chỉ mục bên trái và bên phải của các ký tự.
Đầu ra: In tất cả các hoán vị của chuỗi.
Begin if left = right, then display str else for i := left to right, do swap str[left] and str[i] stringPermutation(str, left+1, right) swap str[left] and str[i] //for backtrack done End
Ví dụ
#include<iostream>
using namespace std;
void stringPermutation(string str, int left, int right) {
if(left == right)
cout << str << endl;
else {
for(int i = left; i<= right; i++) {
swap(str[left], str[i]);
stringPermutation(str, left + 1, right);
swap(str[left], str[i]); //swap back for backtracking
}
}
}
int main() {
string str = "ABC";
cout << "All permutations of " << str << " is: " <<endl<<endl;
stringPermutation(str, 0, str.size()-1);
}
Đầu ra
All permutations of ABC is: ABC ACB BAC BCA CBA CAB