# Largest permutation after at most k swaps

Given a permutation of first n natural numbers as array and an integer k. Print the lexicographically largest permutation after at most k swaps

Examples:

Input: arr[] = {4, 5, 2, 1, 3} k = 3 Output: 5 4 3 2 1 Swap 1st and 2nd elements: 5 4 2 1 3 Swap 3rd and 5th elements: 5 4 3 1 2 Swap 4th and 5th elements: 5 4 3 2 1 Input: arr[] = {2, 1, 3} k = 1 Output: 3 1 2 Swap 1st and 3re elements: 3 1 2

Naive approach: The idea is to generate one by one permutation in lexicographically decreasing order. Compare every generated permutation with original array and count the number of swaps required to convert. If count is less than or equal to k, print this permutation. The problem of this approach is that it would be difficult to implement and will definitely time out for the large value of N.

Algorithm:

1. To find the minimum swaps to convert one array to another.
2. Copy the original array and sort that array in decreasing order. So the sorted array is the largest permutation of the original array.
3. Now generate all permutation in lexicographically decreasing order. Previous permutation is calculated using prev_permutation() function.
4. Find the minimum steps required to convert the new array (permutation in decreasing order) to original array, if the count is less than or equal to k. Then print the array and break.

`#include <bits/stdc++.h>`

`using` `namespace` `std;`

`// Function returns the minimum number`

`// of swaps required to sort the array`

`// This method is taken from below post`

`// minimum-number-swaps-required-sort-array/`

`int` `minSwapsToSort(` `int` `arr[], ` `int` `n)`

`{`

` ` `// Create an array of pairs where first`

` ` `// element is array element and second`

` ` `// element is position of first element`

` ` `pair<` `int` `, ` `int` `> arrPos[n];`

` ` `for` `(` `int` `i = 0; i < n; i++) {`

` ` `arrPos[i].first = arr[i];`

` ` `arrPos[i].second = i;`

` ` `}`

` ` `// Sort the array by array element`

` ` `// values to get right position of`

` ` `// every element as second`

` ` `// element of pair.`

` ` `sort(arrPos, arrPos + n);`

` ` `// To keep track of visited elements.`

` ` `// Initialize all elements as not`

` ` `// visited or false.`

` ` `vector<` `bool` `> vis(n, ` `false` `);`

` ` `// Initialize result`

` ` `int` `ans = 0;`

` ` `// Traverse array elements`

` ` `for` `(` `int` `i = 0; i < n; i++) {`

` ` `// Already swapped and corrected or`

` ` `// already present at correct pos`

` ` `if` `(vis[i] || arrPos[i].second == i)`

` ` `continue` `;`

` ` `// Find out the number of node in`

` ` `// this cycle and add in ans`

` ` `int` `cycle_size = 0;`

` ` `int` `j = i;`

` ` `while` `(!vis[j]) {`

` ` `vis[j] = 1;`

` ` `// move to next node`

` ` `j = arrPos[j].second;`

` ` `cycle_size++;`

` ` `}`

` ` `// Update answer by adding current`

` ` `// cycle.`

` ` `ans += (cycle_size - 1);`

` ` `}`

` ` `// Return result`

` ` `return` `ans;`

`}`

`// method returns minimum number of`

`// swap to make array B same as array A`

`int` `minSwapToMakeArraySame(`

` ` `int` `a[], ` `int` `b[], ` `int` `n)`

`{`

` ` `// Map to store position of elements`

` ` `// in array B we basically store`

` ` `// element to index mapping.`

` ` `map<` `int` `, ` `int` `> mp;`

` ` `for` `(` `int` `i = 0; i < n; i++)`

` ` `mp[b[i]] = i;`

` ` `// now we're storing position of array`

` ` `// A elements in array B.`

` ` `for` `(` `int` `i = 0; i < n; i++)`

` ` `b[i] = mp[a[i]];`

` ` `/* We can uncomment this section to`

` ` `print modified b array`

` ` `for (int i = 0; i < N; i++)`

` ` `cout << b[i] << " ";`

` ` `cout << endl; */`

` ` `// Returing minimum swap for sorting`

` ` `// in modified array B as final answer`

` ` `return` `minSwapsToSort(b, n);`

`}`

`// Function to calculate largest`

`// permutation after atmost K swaps`

`void` `KswapPermutation(`

` ` `int` `arr[], ` `int` `n, ` `int` `k)`

`{`

` ` `int` `a[n];`

` ` `// copy the array`

` ` `for` `(` `int` `i = 0; i < n; i++)`

` ` `a[i] = arr[i];`

` ` `// Sort the array in descending order`

` ` `sort(arr, arr + n, greater<` `int` `>());`

` ` `// generate permutation in lexicographically`

` ` `// decreasing order.`

` ` `do` `{`

` ` `// copy the array`

` ` `int` `a1[n], b1[n];`

` ` `for` `(` `int` `i = 0; i < n; i++) {`

` ` `a1[i] = arr[i];`

` ` `b1[i] = a[i];`

` ` `}`

` ` `// Check if it can be made same in k steps`

` ` `if` `(`

` ` `minSwapToMakeArraySame(`

` ` `a1, b1, n)`

` ` `<= k) {`

` ` `// Print the array`

` ` `for` `(` `int` `i = 0; i < n; i++)`

` ` `cout << arr[i] << ` `" "` `;`

` ` `break` `;`

` ` `}`

` ` `// move to previous permutation`

` ` `} ` `while` `(prev_permutation(arr, arr + n));`

`}`

`int` `main()`

`{`

` ` `int` `arr[] = { 4, 5, 2, 1, 3 };`

` ` `int` `n = ` `sizeof` `(arr) / ` `sizeof` `(arr);`

` ` `int` `k = 3;`

` ` `cout << ` `"Largest permutation after "`

` ` `<< k << ` `" swaps:\n"` `;`

` ` `KswapPermutation(arr, n, k);`

` ` `return` `0;`

`}`

Output:

Largest permutation after 3 swaps: 5 4 3 2 1

Complexity Analysis:

• Time Complexity: O(N!).
To generate all permutation O(N!) time complexity is required.
• Space Complexity: O(n).
to store the new array O(n) space is required.