বিবরণ
প্রথম N নম্বরের পারমিউটেশন ধারণকারী N সংখ্যার একটি অ্যারে দেওয়া আছে। একটি অপারেশনে যেকোনো প্রিফিক্স রিভার্স করা যাবে। টাস্ক হলো মিনিমাম সংখ্যক এমন অপারেশন বের করা যাতে অ্যারেটি ইনক্রিজিং অর্ডারে সোর্ট হয়।
উদাহরণ
যদি অ্যারে = {1, 2, 4, 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
