C++ में STL का उपयोग करके सरणी के सभी रिवर्स परम्यूटेशन

समस्या विवरण

इस खंड में हम देखेंगे कि C++ में STL का उपयोग करके सभी रिवर्स परम्यूटेशन कैसे उत्पन्न करें। (1, 2, 3) जैसे कुछ नंबरों के फॉरवर्ड और रिवर्स परम्यूटेशन इस प्रकार होंगे:

फॉरवर्ड परम्यूटेशन

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

रिवर्स परम्यूटेशन

3, 2, 1
3, 1, 2
2, 3, 1
2, 1, 3
1, 3, 2
1, 2, 3

हम prev_permutation() फंक्शन का उपयोग करके परिणाम प्राप्त करेंगे।

एल्गोरिदम

getPermutation(arr, n):
Begin
    sort arr
    reverse the arr
    repeat
        print array elements
    until previous permutation calculation is not completed
End

उदाहरण

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

void disp(int arr[], int n) {
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void getPermutation(int arr[], int n) {
    sort(arr, arr + n);        // आरोही क्रम में सॉर्ट करें
    reverse(arr, arr + n);     // अवरोही क्रम में रिवर्स करें (सबसे बड़ा परम्यूटेशन)

    cout << "Possible permutations:\n";
    do {
        disp(arr, n);
    } while(prev_permutation(arr, arr + n));  // पिछला परम्यूटेशन जनरेट करें
}

int main() {
    int arr[] = {11, 22, 33, 44};
    int n = sizeof(arr) / sizeof(arr[0]);
    getPermutation(arr, n);
    return 0;
}

आउटपुट

Possible permutations:
44 33 22 11
44 33 11 22
44 22 33 11
44 22 11 33
44 11 33 22
44 11 22 33
33 44 22 11
33 44 11 22
33 22 44 11
33 22 11 44
33 11 44 22
33 11 22 44
22 44 33 11
22 44 11 33
22 33 44 11
22 33 11 44
22 11 44 33
22 11 33 44
11 44 33 22
11 44 22 33
11 33 44 22
11 33 22 44
11 22 44 33
11 22 33 44

महत्वपूर्ण बिंदु

next_permutation() - लेक्सिकोग्राफिकली अगला परम्यूटेशन जनरेट करता है
prev_permutation() - लेक्सिकोग्राफिकली पिछला परम्यूटेशन जनरेट करता है
दोनों फंक्शन्स <algorithm> में हैं
दोनों false लौटाते हैं जब कोई और परम्यूटेशन नहीं होता
शुरू करने से पहले सरणी को सॉर्ट किया जाना चाहिए (next के लिए आरोही, prev के लिए अवरोही)
डुप्लिकेट तत्वों को सही ढंग से हैंडल करता है (यूनिक परम्यूटेशन उत्पन्न करता है)

std::vector के साथ उपयोग

vector<int> v = {1, 2, 3, 4};
sort(v.begin(), v.end(), greater<int>());  // अवरोही क्रम

do {
    for (int x : v) cout << x << " ";
    cout << endl;
} while (prev_permutation(v.begin(), v.end()));

समय जटिलता

O(n! × n) - n! परम्यूटेशन, प्रत्येक को प्रिंट करने में O(n)

चेतावनी

n > 10 के लिए, परम्यूटेशन की संख्या बहुत बड़ी हो जाती है (10! = 3,628,800)। केवल छोटी सरणियों के लिए उपयोग करें।