C++ में पहले N नंबरों के क्रमचय को सॉर्ट करने के लिए न्यूनतम प्रीफिक्स रिवर्सल

विवरण

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