Print k different sorted permutations of a given array in C Program.

Given an array a[] containing N integers, the challenge is to print k different permutations of indices such that the values at those indices form a non-decreasing sequence. Print -1 if it is not possible.

Example

Input: arr[] = {2,5,6,2,2,2,2}, k = 4 Output:    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

Sort the given array and keep track of the original indices of each element. That gives one required permutation. Now if any 2 continuous elements are equal then they can be swapped to get another permutation. Similarly, the third permutation can be generated.

Algorithm

START Step 1 -> Declare Function void indice(int n, pair<int, int> array[])    Loop For int i=0 and i<n and i++       Print array[i].second    End Step 2 -> Declare Function void permutation(int n, int a[], int k)    Use STL pair<int, int> arr[n]    Loop for int i=0 and i<n and i++       Set arr[i].first = a[i]       Set arr[i].second = i    End    Call sort(arr, arr + n)    Declare int count to 1    Loop For int i=1 and i<n and i++       IF (arr[i].first == arr[i - 1].first)          Increment count by 1       End    End    IF count < k       Return -1    End    Loop For int i = 0 and i < k – 1 and i++       Call indice(n, arr)       Loop For int j = 1 and j < n and j++          IF arr[j].first == arr[j - 1].first             Call swap(arr[j], arr[j - 1])             Break          End       End    End    Call indice(n, arr) Step 3 -> In main()    Declare array a[]={2,5,6,2,2,2,2}    Declare int n= sizeof(a)/sizeof(a[0])    Declare int k=4    Call permutation(n,a,k) STOP

Example

#include <bits/stdc++.h> using namespace std; void indice(int n, pair<int, int> array[]){    for (int i = 0; i < n; i++)       cout << array[i].second << " ";    cout << endl; } void permutation(int n, int a[], int k){    pair<int, int> 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; }

Output

if we run above program then it will generate following output

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