Largest permutation after at most k swaps | C ++ 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
#include <bits/stdc++.h> NEW_LINE #include <unordered_map> NEW_LINE using namespace std ; void bestpermutation ( int arr [ ] , int k , int n ) { unordered_map < int , int > h ; for ( int i = 0 ; i < n ; i ++ ) { h . insert ( make_pair ( arr [ i ] , i ) ) ; } if ( n <= k ) { sort ( arr , arr + n , greater < int > ( ) ) ; } else { for ( int j = n ; j >= 1 ; j -- ) { if ( k > 0 ) { int initial_index = h [ j ] ; int best_index = n - j ; if ( initial_index != best_index ) { h [ j ] = best_index ; int element = arr [ best_index ] ; h [ element ] = initial_index ; swap ( arr [ best_index ] , arr [ initial_index ] ) ; k -- ; } } } } } int main ( ) { int arr [ ] = { 3 , 1 , 4 , 2 , 5 } ; int k = 10 ; int n = sizeof ( arr ) / sizeof ( int ) ; bestpermutation ( arr , k , n ) ; cout << " Largest ▁ possible ▁ permutation ▁ after ▁ " << k << " ▁ swaps ▁ is ▁ " ; for ( int i = 0 ; i < n ; i ++ ) cout << arr [ i ] << " ▁ " ; return 0 ; }