विवरण
एन संख्याओं की एक सरणी को देखते हुए जिसमें पहले एन संख्याओं का क्रमपरिवर्तन होता है। एक ही ऑपरेशन में, किसी भी उपसर्ग को उलटा किया जा सकता है। कार्य ऐसे संचालन की न्यूनतम संख्या ज्ञात करना है जैसे कि सरणी में संख्या बढ़ते क्रम में क्रमबद्ध हो।
उदाहरण
यदि सरणी {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