Hiểu bài toán

Cho một chuỗi s, nhiệm vụ là tạo ra tất cả các chuỗi mới có thể tạo thành từ các ký tự của s, sao cho mỗi chuỗi mới có độ dài bằng s. Các chuỗi này phải là các cách sắp xếp lại (permutation) của các ký tự trong s. Do đó, bài toán yêu cầu liệt kê tất cả các xâu kí tự khác nhau tạo thành bằng cách sắp xếp lại các kí tự của s, và in ra số lượng của chúng cùng các xâu đó.

Ví dụ: Với s = "aabac", ta cần liệt kê tất cả các cách sắp xếp lại của 5 ký tự này. Vì có ký tự lặp lại (a xuất hiện 3 lần, b 1 lần, c 1 lần), ta cần loại bỏ các trường hợp trùng lặp.

Các cách tiếp cận

Cách Sử dụng thư viện chuẩn (next_permutation)

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

int main() {
    string s;
    cin >> s;

    sort(s.begin(), s.end());
    vector<string> res;

    do {
        res.push_back(s);
    } while (next_permutation(s.begin(), s.end()));

    cout << res.size() << "\n";
    for (auto &x : res) cout << x << "\n";

    return 0;
}

• Time Complexity: O(N * N!)
• Space Complexity: O(N * N!)

Đây là cách tiếp cận trực quan nhất利用 C++ STL.

1. Chuỗi s được sắp xếp lại (sort) để đảm bảo bắt đầu từ permutation nhỏ nhất theo thứ tự từ điển.
2. Sử dụng hàm next_permutation trong một vòng lặp do-while. Hàm này tự động sắp xếp lại chuỗi thành permutation tiếp theo theo thứ tự từ điển. Nếu chuỗi hiện tại là permutation cuối cùng, hàm trả về false.
3. Mỗi permutation được sinh ra lưu vào một vector.
4. Sau đó in ra kích thước vector và tất cả các phần tử. Cách này rất ngắn gọn và dễ hiểu, nhưng tốn bộ nhớ để lưu trữ tất cả các kết quả trước khi in.

Cách Tối ưu hóa in kết quả

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    string s;
    cin>>s;
    sort(s.begin(),s.end());
    int count=0;
    do {
        count++;
    } while (next_permutation(s.begin(),s.end()));
    cout<<count<<endl;
    do {
        cout<<s<<endl;
    } while (next_permutation(s.begin(),s.end()));
}

• Time Complexity: O(N * N!)
• Space Complexity: O(N)

Đây là biến thể của cách tiếp cận đầu tiên nhưng tối ưu hơn về mặt không gian bộ nhớ.

1. Thay vì lưu tất cả các xâu vào vector, ta thực hiện vòng lặp do-while hai lần.
2. Lần lặp đầu tiên: Đếm số lượng permutation (biến count).
3. In ra số lượng.
4. Lần lặp thứ hai: In trực tiếp từng permutation ra màn hình. Cách này không cần lưu trữ mảng kết quả trung gian, chỉ cần O(N) bộ nhớ cho chuỗi s hiện tại, phù hợp hơn với giới hạn bộ nhớ.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán yêu cầu liệt kê các hoán vị của một multiset (tập hợp có phần tử lặp lại).
• Thuật toán next_permutation của C++ xử lý rất tốt trường hợp có phần tử lặp lại, tự động bỏ qua các hoán vị trùng lặp nếu chuỗi đầu vào được sắp xếp.
• Cần phải sắp xếp chuỗi ban đầu trước khi bắt đầu sinh hoán vị để đảm bảo liệt kê đầy đủ và theo thứ tự từ điển.

Lỗi thường gặp

• Quên sắp xếp chuỗi ban đầu (sort(s.begin(), s.end()))会导致 không thể sinh ra đầy đủ các hoán vị hoặc không thể sử dụng next_permutation chính xác.
• Sử dụng cin >> s thay vì getline(cin, s) có thể bỏ qua các khoảng trắng nếu đề bài yêu cầu chuỗi có thể chứa khoảng trắng (trong bài này chỉ toàn ký tự chữ nên cin không vấn đề, nhưng là lỗi thường gặp).
• Nếu tựImplement thuật toán sinh hoán vị thủ công mà không xử lý đúng các ký tự giống nhau, sẽ bị in ra các xâu trùng lặp.