Largest permutation after at most k swaps | Java Program to find the largest permutation after at most k swaps using unordered_map . ; Function to find the largest permutation after k swaps ; Storing the elements and their index in map ; If number of swaps allowed are equal to number of elements then the resulting permutation will be descending order of given permutation . ; if j is not at it 's best index ; Change the index of the element which was at position 0. Swap the element basically . ; decrement number of swaps ; Driver code ; K is the number of swaps ; n is the size of the array ; Function calling
import java . util . * ; class GFG { static void bestpermutation ( ArrayList < Integer > arr , int k , int n ) { HashMap < Integer , Integer > h = new HashMap < Integer , Integer > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { h . put ( arr . get ( i ) , i ) ; } if ( n <= k ) { Collections . sort ( arr , Collections . reverseOrder ( ) ) ; } else { for ( int j = n ; j >= 1 ; j -- ) { if ( k > 0 ) { int initial_index = h . get ( j ) ; int best_index = n - j ; if ( initial_index != best_index ) { h . put ( j , best_index ) ; int element = arr . get ( best_index ) ; h . put ( element , initial_index ) ; int temp = arr . get ( best_index ) ; arr . set ( best_index , arr . get ( initial_index ) ) ; arr . set ( initial_index , temp ) ; k -- ; } } } } } public static void main ( String [ ] args ) { ArrayList < Integer > arr = new ArrayList < Integer > ( ) ; arr . add ( 3 ) ; arr . add ( 1 ) ; arr . add ( 4 ) ; arr . add ( 2 ) ; arr . add ( 5 ) ; int k = 10 ; int n = arr . size ( ) ; bestpermutation ( arr , k , n ) ; System . out . print ( " Largest ▁ possible ▁ permutation ▁ after ▁ " + k + " ▁ swaps ▁ is ▁ " ) ; for ( int i = 0 ; i < n ; i ++ ) System . out . print ( arr . get ( i ) + " ▁ " ) ; } }