Print k different sorted permutations of a given array | C ++ implementation of the approach ; Utility function to print the original indices of the elements of the array ; Function to print the required permutations ; To keep track of original indices ; Sort the array ; Count the number of swaps that can be made ; Cannot generate 3 permutations ; Print the first permutation ; Find an index to swap and create second permutation ; Print the last permutation ; Driver code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int next_pos = 1 ; void printIndices ( int n , pair < int , int > a [ ] ) { for ( int i = 0 ; i < n ; i ++ ) cout << a [ i ] . second << " ▁ " ; cout << endl ; } void printPermutations ( 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 ++ ) { printIndices ( n , arr ) ; for ( int j = next_pos ; j < n ; j ++ ) { if ( arr [ j ] . first == arr [ j - 1 ] . first ) { swap ( arr [ j ] , arr [ j - 1 ] ) ; next_pos = j + 1 ; break ; } } } printIndices ( n , arr ) ; } int main ( ) { int a [ ] = { 1 , 3 , 3 , 1 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int k = 3 ; printPermutations ( n , a , k ) ; return 0 ; }