Efficient approach: This is a greedy approach. The largest permutation is found when the largest elements are at the front of the array, i.e. the largest elements are sorted in decreasing order. There are at most k swaps so put the 1st, 2nd, 3rd, …, kth largest element at their respective position.
Note: If the number of swaps allowed is equal to the size of the array, then there is no need to iterate over the whole array. The answer will simply be the reverse sorted array.
Algorithm:
- Create a HashMap or an array of length n to store element-index pair or map element to its index.
- Now run a loop k times.
- In each iteration swap the ith element with the element n – i. where i is the index or count of the loop. Also swap their position, i.e. update the hashmap or array. So in this step the largest element in remaining element is swapped to the front.
- Print the output array.
Implementation 1: This uses simple arrays to arrive at the solution.
// Below is C++ code to print largest
// permutation after at most K swaps
#include <bits/stdc++.h>
using namespace std;
// Function to calculate largest
// permutation after atmost K swaps
void KswapPermutation(
int arr[], int n, int k)
{
// Auxiliary dictionary of
// storing the position of elements
int pos[n + 1];
for ( int i = 0; i < n; ++i)
pos[arr[i]] = i;
for ( int i = 0; i < n && k; ++i) {
// If element is already i'th largest,
// then no need to swap
if (arr[i] == n - i)
continue ;
// Find position of i'th
// largest value, n-i
int temp = pos[n - i];
// Swap the elements position
pos[arr[i]] = pos[n - i];
pos[n - i] = i;
// Swap the ith largest value with the
// current value at ith place
swap(arr[temp], arr[i]);
// decrement number of swaps
--k;
}
}
// Driver code
int main()
{
int arr[] = { 4, 5, 2, 1, 3 };
int n = sizeof (arr) / sizeof (arr[0]);
int k = 3;
KswapPermutation(arr, n, k);
cout << "Largest permutation after "
<< k << " swaps:n" ;
for ( int i = 0; i < n; ++i)
printf ( "%d " , arr[i]);
return 0;
}
Output:
Largest permutation after 3 swaps: 5 4 3 2 1
Implementation 2: This uses a hashmap to arrive at the solution.
// C++ Program to find the
// largest permutation after
// at most k swaps using unordered_map.
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
// Function to find the largest
// permutation after k swaps
void bestpermutation(
int arr[], int k, int n)
{
// Storing the elements and
// their index in map
unordered_map< int , int > h;
for ( int i = 0; i < n; i++) {
h.insert(make_pair(arr[i], i));
}
// If number of swaps allowed
// are equal to number of elements
// then the resulting permutation
// will be descending order of
// given permutation.
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 j is not at it's best index
if (initial_index != best_index) {
h[j] = best_index;
// Change the index of the element
// which was at position 0. Swap
// the element basically.
int element = arr[best_index];
h[element] = initial_index;
swap(
arr[best_index],
arr[initial_index]);
// decrement number of swaps
k--;
}
}
}
}
}
// Driver code
int main()
{
int arr[] = { 3, 1, 4, 2, 5 };
// K is the number of swaps
int k = 10;
// n is the size of the array
int n = sizeof (arr) / sizeof ( int );
// Function calling
bestpermutation(arr, k, n);
cout << "Largest possible permutation after "
<< k << " swaps is " ;
for ( int i = 0; i < n; i++)
cout << arr[i] << " " ;
return 0;
}
Output:
Largest possible permutation after 10 swaps is 5 4 3 2 1
Complexity Analysis:
-
Time Complexity: O(N).
Only one traversal of the array is required. -
Space Complexity: O(n).
To store the new array O(n) space is required.