Số lần đảo ngược tiền tố tối thiểu để sắp xếp hoán vị N số đầu tiên trong C++

Mô tả

Cho mảng N số là hoán vị của N số đầu tiên. Trong một phép toán, bất kỳ tiền tố nào cũng có thể bị đảo ngược. Nhiệm vụ là tìm số phép toán tối thiểu như vậy để các số trong mảng được sắp xếp theo thứ tự tăng dần.

Ví dụ

Nếu mảng là {1, 2, 4, 3} thì cần tối thiểu 3 bước để sắp xếp mảng tăng dần:

• Đảo toàn bộ mảng {3, 4, 2, 1}
• Đảo 2 phần tử đầu {4, 3, 2, 1}
• Đảo toàn bộ mảng {1, 2, 3, 4}

Thuật toán

• Mã hóa các số cho trước thành chuỗi. Sắp xếp mảng và mã hóa thành chuỗi đích.
• Thực hiện BFS từ hoán vị ban đầu. Mỗi lần, kiểm tra tất cả hoán vị do đảo ngược tiền tố của hoán vị hiện tại tạo ra.
• Nếu chưa thăm, đưa vào hàng đợi với số lần đảo ngược đã làm.
• Khi hoán vị của chuỗi mã hóa trùng với chuỗi đích, trả về số lần đảo ngược cần để đến đây.
• Đó là, tất cả hoán vị của chuỗi được thực hiện và giá trị tối thiểu trong đó được trả về làm đáp án.

Ví dụ

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int minimumPrefixReversals(int *a, int n) {
    string start = "";
    string destination = "", t, r;
    for (int i = 0; i < n; i++) {
        start += to_string(a[i]);
    }
    sort(a, a + n);
    for (int i = 0; i < n; i++) destination += to_string(a[i]);
    queue<pair<string, int> > qu;
    pair<string, int> p;
    qu.push(make_pair(start, 0));
    if (start == destination) {
        return 0;
    }
    while (!qu.empty()) {
        p = qu.front();
        t = p.first;
        qu.pop();
        for (int j = 2; j <= n; j++) {
            r = t;
            reverse(r.begin(), r.begin() + j);
            if (r == destination) {
                return p.second + 1;
            }
            qu.push(make_pair(r, p.second + 1));
        }
    }
}
int main() {
    int a[] = { 1, 2, 4, 3 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << "Số lần đảo ngược tối thiểu: " << minimumPrefixReversals(a, n) << endl;
    return 0;
}

Kết quả

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:

Số lần đảo ngược tối thiểu: 3