Tạo tất cả hoán vị ngược của mảng dùng STL trong C++

Sinh tất cả hoán vị ngược (reverse permutations) của mảng dùng STL. Với dãy (1,2,3):

Hoán vị xuôi (forward)

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Hoán vị ngược (reverse)

3 2 1
3 1 2
2 3 1
2 1 3
1 3 2
1 2 3

Sử dụng prev_permutation() thay vì next_permutation().

Thuật toán

1. Sắp xếp mảng tăng dần.
2. Đảo ngược mảng (để bắt đầu từ hoán vị lớn nhất).
3. Lặp: in mảng, sau đó gọi prev_permutation() cho đến khi trả về false.

Code ví dụ

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

void display(int arr[], int n) {
    for(int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

void getReversePermutations(int arr[], int n) {
    sort(arr, arr + n);      // Sắp xếp tăng
    reverse(arr, arr + n);   // Đảo ngược -> hoán vị lớn nhất
    
    cout << "Cac hoan vi nguoc:\n";
    do {
        display(arr, n);
    } while(prev_permutation(arr, arr + n));
}

int main() {
    int arr[] = {11, 22, 33, 44};
    int n = sizeof(arr) / sizeof(arr[0]);
    getReversePermutations(arr, n);
    return 0;
}

Kết quả (rút gọn)

Cac hoan vi nguoc:
44 33 22 11
44 33 11 22
44 22 33 11
44 22 11 33
44 11 33 22
44 11 22 33
33 44 22 11
...
11 22 33 44

Tổng cộng 4! = 24 hoán vị.

Lưu ý quan trọng

• prev_permutation sinh hoán vị trước đó theo thứ tự từ điển.
• Phải bắt đầu từ hoán vị lớn nhất (giảm dần) để sinh hết.
• Nếu bắt đầu từ mảng bất kỳ, nó chỉ sinh các hoán vị "trước" mảng đó.
• Độ phức tạp: O(n!) - chỉ dùng cho n nhỏ (n ≤ 10).

So sánh next_permutation vs prev_permutation