Trong bài toán này, chúng ta được cung cấp một chuỗi. Nhiệm vụ của chúng ta là tạo một chương trình c để in tất cả các hoán vị của một chuỗi đã cho.
Chương trình này sẽ tìm tất cả các kết hợp có thể có của chuỗi đã cho và in chúng.
Hoán vị là sự sắp xếp của tất cả các bộ phận của một đối tượng, theo tất cả các thứ tự sắp xếp có thể có.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
xyz
Đầu ra
xyz, xzy, yxz, yzx, zxy, zyx
Giải thích
These are all permutations take in order.
Để giải quyết vấn đề này, chúng ta sẽ sử dụng backtracking tức là lấy từng ký tự của chuỗi làm ký tự đầu tiên của hoán vị và sau đó lần lượt chọn tất cả các ký tự còn lại của chuỗi. Và do đó, in tất cả các hoán vị của chuỗi.
Chương trình in tất cả các hoán vị của một chuỗi đã cho
// Chương trình in tất cả các hoán vị của một chuỗi đã cho -
Ví dụ
#include <iostream>
using namespace std;
void findPermutations(string str, int l, int r){
if (l == r)
cout<<str<<" ";
else{
for (int i = l; i <= r; i++){
swap(str[l], str[i]);
findPermutations(str, l+1, r);
swap(str[l], str[i]);
}
}
}
int main(){
string str = "WXYZ";
int n = str.size();
findPermutations(str, 0, n-1);
return 0;
} Đầu ra
WXYZ WXZY WYXZ WYZX WZYX WZXY XWYZ XWZY XYWZ XYZW XZYW XZWY YXWZ YXZW YWXZ YWZX YZWX YZXW ZXYW ZXWY ZYXW ZYWX ZWYX ZWXY