Largest permutation after at most k swaps

Software Development
#1

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[0]);

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.