C++ में लेक्सिकोग्राफिकली नेक्स्ट पर्मुटेशन

लेक्सिकोग्राफिकली नेक्स्ट पर्मुटेशन

यहां हम देखेंगे कि C++ में स्ट्रिंग के लेक्सिकोग्राफिकली नेक्स्ट पर्मुटेशन को कैसे जनरेट करें। लेक्सिकोग्राफिकली नेक्स्ट पर्मुटेशन मूल रूप से बड़ा पर्मुटेशन है। उदाहरण के लिए, "ACB" का नेक्स्ट "BAC" होगा। कुछ मामलों में, लेक्सिकोग्राफिकली नेक्स्ट पर्मुटेशन मौजूद नहीं होता, जैसे "BBB" या "DCBA" आदि।

C++ लाइब्रेरी फ़ंक्शन: next_permutation()

C++ में हम <algorithm> हेडर फाइल में मौजूद next_permutation() लाइब्रेरी फ़ंक्शन का उपयोग करके इसे कर सकते हैं।

सिंटैक्स

bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

यह फ़ंक्शन रेंज को लेक्सिकोग्राफिकली अगले पर्मुटेशन में पुनर्व्यवस्थित करता है। यदि ऐसा पर्मुटेशन मौजूद है तो true रिटर्न करता है, अन्यथा रेंज को पहले पर्मुटेशन (सॉर्टेड ऑर्डर) में बदल देता है और false रिटर्न करता है।

उदाहरण

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main() {
    string s = "DBAC";
    cout << "Original: " << s << endl;
    
    for (int i = 0; i < 5; i++) {
        bool val = next_permutation(s.begin(), s.end());
        if (val == false) {
            cout << "No next permutation" << endl;
            break;
        } else {
            cout << "Next: " << s << endl;
        }
    }
    return 0;
}

आउटपुट

Original: DBAC
Next: DBCA
Next: DCAB
Next: DCBA
No next permutation

prev_permutation()

इसी तरह, prev_permutation() लेक्सिकोग्राफिकली पिछला पर्मुटेशन ढूंढता है।

उदाहरण: सभी पर्मुटेशन्स जनरेट करना

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int main() {
    string s = "ABC";
    sort(s.begin(), s.end());  // पहले पर्मुटेशन से शुरू करें
    
    cout << "All permutations of " << s << ":\n";
    do {
        cout << s << endl;
    } while (next_permutation(s.begin(), s.end()));
    
    return 0;
}

आउटपुट

All permutations of ABC:
ABC
ACB
BAC
BCA
CAB
CBA

कस्टम कम्पेरेटर के साथ

// डिसेंडिंग ऑर्डर में पर्मुटेशन्स
string s = "ABC";
sort(s.begin(), s.end(), greater<char>());
do {
    cout << s << endl;
} while (prev_permutation(s.begin(), s.end(), greater<char>()));

समय जटिलता

• अमॉर्टाइज्ड O(1) प्रति पर्मुटेशन
• सबसे खराब स्थिति O(n) प्रति कॉल जहां n सीक्वेंस की लंबाई है
• सभी पर्मुटेशन्स जनरेट करने के लिए कुल O(n!)