In tất cả hoán vị của chuỗi trong C

Cho chuỗi. In tất cả hoán vị (permutation) của chuỗi đó.

Ví dụ

Đầu vào - "xyz"

Đầu ra - xyz, xzy, yxz, yzx, zxy, zyx

Phương pháp Backtracking

• Fix ký tự tại vị trí l, hoán vị với các vị trí i từ l đến r
• Đệ quy cho vị trí l+1
• Backtrack: hoán vị ngược lại để khôi phục

Chương trình mẫu (C++)

#include <iostream>
#include <string>
using namespace std;

void permute(string str, int l, int r) {
    if (l == r)
        cout << str << " ";
    else {
        for (int i = l; i <= r; i++) {
            swap(str[l], str[i]);
            permute(str, l+1, r);
            swap(str[l], str[i]); // backtrack
        }
    }
}

int main() {
    string str = "WXYZ";
    int n = str.size();
    permute(str, 0, n-1);
    return 0;
}

Kết quả

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

Lưu ý: Số hoán vị = n! (thành nhanh). Chuỗi dài > 10 sẽ rất chậm. C++ dùng string thuận tiện hơn C char[].