C प्रोग्राम में दिए गए ऐरे के k अलग-अलग सॉर्टेड क्रमपरिवर्तन प्रिंट करें

समस्या विवरण

एक ऐरे a[] दिया गया है जिसमें N पूर्णांक हैं, चुनौती k अलग-अलग इंडेक्स के क्रमपरिवर्तन प्रिंट करना है ताकि उन इंडेक्स पर मान गैर-घटते क्रम में हों। यदि संभव न हो तो -1 प्रिंट करें।

उदाहरण

इनपुट: arr[] = {2,5,6,2,2,2,2}, k = 4
आउटपुट:
0 3 4 5 6 1 2
3 0 4 5 6 1 2
0 3 4 5 6 1 2
3 0 4 5 6 1 2

दिए गए ऐरे को सॉर्ट करें और प्रत्येक तत्व के मूल इंडेक्स को ट्रैक रखें। यह एक आवश्यक क्रमपरिवर्तन देता है। अब यदि कोई 2 लगातार तत्व बराबर हैं तो उन्हें स्वैप करके दूसरा क्रमपरिवर्तन प्राप्त किया जा सकता है। इसी तरह, तीसरा क्रमपरिवर्तन उत्पन्न किया जा सकता है।

एल्गोरिदम

शुरुआत
चरण 1: void indice(int n, pair array[]) फंक्शन घोषित करें
    i = 0 से n-1 तक लूप
        array[i].second प्रिंट करें
    अंत
चरण 2: void permutation(int n, int a[], int k) फंक्शन घोषित करें
    STL pair arr[n] उपयोग करें
    i = 0 से n-1 तक लूप
        arr[i].first = a[i] सेट करें
        arr[i].second = i सेट करें
    अंत
    sort(arr, arr + n) कॉल करें
    int count को 1 घोषित करें
    i = 1 से n-1 तक लूप
        यदि (arr[i].first == arr[i-1].first) तो
            count को 1 से बढ़ाएं
        अंत
    अंत
    यदि count < k तो
        -1 वापस करें
    अंत
    i = 0 से k-2 तक लूप
        indice(n, arr) कॉल करें
        j = 1 से n-1 तक लूप
            यदि arr[j].first == arr[j-1].first तो
                swap(arr[j], arr[j-1]) कॉल करें
                ब्रेक
            अंत
        अंत
    अंत
    indice(n, arr) कॉल करें
चरण 3: main() में
    array a[] = {2,5,6,2,2,2,2} घोषित करें
    int n = sizeof(a)/sizeof(a[0]) घोषित करें
    int k = 4 घोषित करें
    permutation(n, a, k) कॉल करें
रोकें

C++ प्रोग्राम उदाहरण

#include <bits/stdc++.h>
using namespace std;

void indice(int n, pair array[]){
    for (int i = 0; i < n; i++)
        cout << array[i].second << " ";
    cout << endl;
}

void permutation(int n, int a[], int k){
    pair arr[n];
    for (int i = 0; i < n; i++){
        arr[i].first = a[i];
        arr[i].second = i;
    }
    sort(arr, arr + n);
    int count = 1;
    for (int i = 1; i < n; i++)
        if (arr[i].first == arr[i-1].first)
            count++;
    if (count < k){
        cout << "-1";
        return;
    }
    for (int i = 0; i < k - 1; i++){
        indice(n, arr);
        for (int j = 1; j < n; j++){
            if (arr[j].first == arr[j-1].first){
                swap(arr[j], arr[j-1]);
                break;
            }
        }
    }
    indice(n, arr);
}

int main(){
    int a[] = {2,5,6,2,2,2,2};
    int n = sizeof(a) / sizeof(a[0]);
    int k = 4;
    permutation(n, a, k);
    return 0;
}

आउटपुट

उपरोक्त प्रोग्राम चलाने पर निम्नलिखित आउटपुट उत्पन्न होगा:

0 3 4 5 6 1 2
3 0 4 5 6 1 2
0 3 4 5 6 1 2
3 0 4 5 6 1 2