คำอธิบาย
กำหนดอาร์เรย์ของตัวเลข N ซึ่งมีการเรียงสับเปลี่ยนของตัวเลข N ตัวแรก ในการดำเนินการเดียว คำนำหน้าใดๆ สามารถย้อนกลับได้ ภารกิจคือการค้นหาจำนวนขั้นต่ำของการดำเนินการดังกล่าวเพื่อให้ตัวเลขในอาร์เรย์เรียงลำดับเพิ่มขึ้น
ตัวอย่าง
หากอาร์เรย์เป็น {1, 2, 4, 3} อย่างน้อย 3 ขั้นตอนที่จำเป็นในการจัดเรียงอาร์เรย์ในลำดับที่เพิ่มขึ้น -
- ย้อนกลับทั้งอาร์เรย์ {3, 4, 2, 1}
- ย้อนกลับสององค์ประกอบแรก 4/ 3, 2, 1}
- ย้อนกลับทั้งอาร์เรย์ {1, 2, 3, 4}
อัลกอริทึม
- เข้ารหัสตัวเลขที่ระบุเป็นสตริง จัดเรียงอาร์เรย์และเข้ารหัสเป็นสตริงปลายทาง
- จากนั้นทำ BFS จากการเปลี่ยนลำดับเริ่มต้น แต่ละครั้ง ให้ตรวจสอบการเรียงสับเปลี่ยนทั้งหมดที่เกิดจากการเปลี่ยนคำนำหน้าของการเรียงสับเปลี่ยนปัจจุบัน
- หากไม่มา ให้จัดคิวโดยนับการกลับรายการเสร็จสิ้น
- เมื่อการเรียงสับเปลี่ยนของสตริงที่เข้ารหัสเหมือนกับสตริงปลายทาง ให้ส่งคืนจำนวนการกลับรายการที่จำเป็นเพื่อไปถึงที่นี่
- นั่นคือ การเรียงสับเปลี่ยนของสตริงทั้งหมดเสร็จสิ้น และค่าที่น้อยที่สุดจะถูกส่งคืนเป็นคำตอบ
ตัวอย่าง
#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 << "Minimum reversal: " << minimumPrefixReversals(a, n) << endl;
return 0;
} ผลลัพธ์
เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
Minimum reversal: 3
