Hoán vị lớn nhất sau tối đa K lần swap C++

Cho mảng 1..N (hoán vị) và số K. Tối đa K lần hoán vị 2 phần tử bất kỳ. Tìm hoán vị lớn nhất theo thứ tự từ điển.

Thuật toán Tham lam

• Mục tiêu: đưa số lớn nhất về đầu, số lớn thứ 2 về vị trí 2,...
• Với i = 0..N-1 và K > 0:
  • Số mong muốn tại vị trí i là N-i.
  • Nếu đã đúng chỗ → bỏ qua.
  • Ngược lại: tìm vị trí của N-i, hoán vị với i, K--.

Triển khai C++

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

void largestPermutationKSwaps(vector& arr, int k) {
    int n = arr.size();
    vector pos(n + 1);
    for (int i = 0; i < n; i++) pos[arr[i]] = i;

    for (int i = 0; i < n && k > 0; i++) {
        int desired = n - i;
        if (arr[i] == desired) continue;
        int idx = pos[desired];
        pos[arr[i]] = idx;
        swap(arr[i], arr[idx]);
        k--;
    }
}

int main() {
    vector arr = {5, 3, 2, 6, 7, 1, 4};
    largestPermutationKSwaps(arr, 3);
    for (int x : arr) cout << x; // 7653214
    return 0;
}

Kết quả

7653214