In tất cả hoán vị của chuỗi (Print all permutations)

Giới thiệu

In tất cả hoán vị của một chuỗi cho trước là ví dụ của bài toán backtracking (quay lui). Ta sẽ giảm kích thước chuỗi con để giải các bài toán con, sau đó quay lui để lấy hoán vị khác từ phần đó.

Ví dụ, nếu chuỗi là ABC, tất 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!). Đây là độ phức tạp rất lớn. Khi kích thước chuỗi tăng, nó mất thời gian lâu hơn để hoàn thành nhiệm vụ.

Đầu vào và Đầu ra

Đầu vào: Một chuỗi "ABC"
Đầu ra: Tất cả hoán vị của ABC là: ABC ACB BAC BCA CBA CAB

Thuật toán

stringPermutation(str, left, right)
Đầu vào: Chuỗi và chỉ số trái và phải của ký tự.
Đầu ra: In tất cả hoán vị của chuỗi.

Begin
    if left = right, then
        hiển thị str
    else
        for i := left to right, do
            hoán đổi str[left] và str[i]
            stringPermutation(str, left+1, right)
            hoán đổi str[left] và str[i]  // cho backtrack
        done
End

Ví dụ (C++)

#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]); // hoán đổi lại cho backtracking
        }
    }
}

int main() {
    string str = "ABC";
    cout << "All permutations of " << str << " is: " << endl << endl;
    stringPermutation(str, 0, str.size()-1);
}

Kết quả

All permutations of ABC is:
ABC
ACB
BAC
BCA
CBA
CAB