Print k different sorted permutations of a given array | Java implementation of the approach ; Utility function to print the original indices of the elements of the array ; Used for sorting in ascending order ; 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
import java . util . * ; class GFG { static int next_pos = 1 ; static class pair { int first , second ; pair ( ) { first = 0 ; second = 0 ; } } static void printIndices ( int n , pair a [ ] ) { for ( int i = 0 ; i < n ; i ++ ) System . out . print ( a [ i ] . second + " ▁ " ) ; System . out . println ( ) ; } static class sort implements Comparator < pair > { public int compare ( pair a , pair b ) { return a . first < b . first ? - 1 : 1 ; } } static void printPermutations ( int n , int a [ ] , int k ) { pair arr [ ] = new pair [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { arr [ i ] = new pair ( ) ; arr [ i ] . first = a [ i ] ; arr [ i ] . second = i ; } Arrays . sort ( arr , new sort ( ) ) ; int count = 1 ; for ( int i = 1 ; i < n ; i ++ ) if ( arr [ i ] . first == arr [ i - 1 ] . first ) count ++ ; if ( count < k ) { System . out . print ( " - 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 ) { pair t = arr [ j ] ; arr [ j ] = arr [ j - 1 ] ; arr [ j - 1 ] = t ; next_pos = j + 1 ; break ; } } } printIndices ( n , arr ) ; } public static void main ( String arsg [ ] ) { int a [ ] = { 1 , 3 , 3 , 1 } ; int n = a . length ; int k = 3 ; printPermutations ( n , a , k ) ; } }