বিবরণ
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
