Largest permutation after at most k swaps

Largest permutation after at most k swaps
https://www.hackerrank.com/challenges/largest-permutation
https://www.codechef.com/problems/SWAPERM

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

Input: arr[] = {4, 5, 2, 1, 3}
       k = 3
Output: 5 4 3 2 1
Explanation:
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 

Time complexity: O(n)

Auxiliary space: O(n)

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;

    }

}

X. Backtrack
http://www.geeksforgeeks.org/find-maximum-number-possible-by-doing-at-most-k-swaps/

Given a positive integer, find maximum integer possible by doing at-most K swap operations on its digits.

Idea is to consider every digit and swap it with digits following it one at a time and see if it leads to the maximum number. We repeat the process K times. The code can be further optimized if we swap only if current digit is less than the following digit.

void findMaximumNum(string str, int k, string& max)

{

    // return if no swaps left

    if(k == 0)

        return;

 

    int n = str.length();

     

    // consider every digit

    for (int i = 0; i < n - 1; i++)

    {

      

        // and compare it with all digits after it

        for (int j = i + 1; j < n; j++)

        {

            // if digit at position i is less than digit

            // at position j, swap it and check for maximum

            // number so far and recurse for remaining swaps

            if (str[i] < str[j])

            {

                // swap str[i] with str[j]

                swap(str[i], str[j]);

 

                // If current num is more than maximum so far

                if (str.compare(max) > 0)

                    max = str;

 

                // recurse of the other k - 1 swaps

                findMaximumNum(str, k - 1, max);

 

                // backtrack

                swap(str[i], str[j]);

            }

        }

    }

}

1. Find minimum integer possible by doing at-least K swap operations on its digits.
2. Find maximum/minimum integer possible by doing exactly K swap operations on its digits.

Largest permutation after at most k swaps