C++ Hoán vị của chuỗi dùng STL

Hoán vị của chuỗi là sắp xếp lại các ký tự. In tất cả hoán vị của chuỗi dùng STL C++. Ví dụ:

Input: "ADT" → Output: ADT, ATD, DAT, DTA, TAD, TDA

Phương pháp 1: rotate()

Dùng rotate() của STL kết hợp đệ quy.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

void permutations(string s, string ans) {
    if (s.empty()) {
        cout << ans << "\n";
        return;
    }
    for (int i = 0; i < (int)s.size(); i++) {
        permutations(s.substr(1), ans + s[0]);
        rotate(s.begin(), s.begin()+1, s.end());
    }
}

int main() {
    string s = "ADT";
    permutations(s, "");
    return 0;
}

Kết quả

ADT ATD DTA DAT TAD TDA

Phương pháp 2: next_permutation()

Sắp xếp chuỗi theo thứ tự từ điển, sau đó dùng next_permutation() lặp cho đến khi trả về false.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s = "ADT";
    sort(s.begin(), s.end());
    do {
        cout << s << "\n";
    } while (next_permutation(s.begin(), s.end()));
    return 0;
}

Kết quả

ADT ATD DAT DTA TAD TDA

Kết luận

Đã trình bày 2 cách in hoán vị chuỗi bằng STL: rotate() đệ quy và next_permutation() lặp. C++ STL rất mạnh cho bài toán này. Hy vọng hữu ích.