Hoán vị tiếp theo theo thứ tự từ điển (next_permutation) trong C++

Hàm std::next_permutation() trong header <algorithm> sắp xếp lại các phần tử thành hoán vị tiếp theo theo thứ tự từ điển (lexicographically). Trả về true nếu có hoán vị tiếp theo, false nếu đã ở hoán vị cuối cùng.

Cú pháp

bool next_permutation(BidirIt first, BidirIt last);
bool next_permutation(BidirIt first, BidirIt last, Compare comp);

Ví dụ: Chuỗi "DBAC"

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main() {
    string s = "DBAC";
    
    cout << "Ban dau: " << s << endl;
    
    for (int i = 0; i < 5; i++) {
        bool has_next = next_permutation(s.begin(), s.end());
        if (!has_next) {
            cout << "Khong co hoan vi tiep theo" << endl;
            break;
        }
        cout << "Tiep theo: " << s << endl;
    }
}

Kết quả

Ban dau: DBAC
Tiep theo: DBCA
Tiep theo: DCAB
Tiep theo: DCBA
Khong co hoan vi tiep theo

Thuật toán đằng sau (C++ reference implementation)

1. Tìm chỉ số i lớn nhất sao cho s[i] < s[i+1]
2. Nếu không tìm thấy → đã ở hoán vị cuối → trả về false
3. Tìm chỉ số j lớn nhất sao cho s[j] > s[i]
4. Hoán đổi s[i] và s[j]
5. Đảo ngược dãy từ i+1 đến cuối

Ví dụ: Tạo tất cả hoán vị của "ABC"

#include <iostream>
#include <algorithm>
#include <string>

int main() {
    string s = "ABC";
    sort(s.begin(), s.end());  // Bắt đầu từ hoán vị nhỏ nhất
    
    do {
        cout << s << endl;
    } while (next_permutation(s.begin(), s.end()));
}

Kết quả

ABC
ACB
BAC
BCA
CAB
CBA

Lưu ý quan trọng

• Phạm vi phải hỗ trợ iterator ngẫu nhiên hoặc hai chiều (bidirectional)
• Để sinh tất cả hoán vị, hãy sort() trước
• Có phiên bản prev_permutation() cho hoán vị trước
• Độ phức tạp: O(n) cho mỗi lần gọi

Ứng dụng thực tế

• Giải bài toán du lịch thương nhân (TSP) brute-force
• Sinh test case cho thuật toán
• Thuật toán backtracking cần duyệt hoán vị