In this problem, one positive integer string is given, we have to find
the permutation whose value is maximum by swapping digits’ k times,
into different places.
We will solve this problem by choosing a digit and swap it with digits
following it one at a time to find a maximum number. We repeat the
process k times. The backtracking strategy is working here because
when we find a number which is not greater than the previous value, we
backtrack to old value and check again.
Input and Output
Input:
A number of multiple digits.
The input is: 129814999
Output:
The maximum value from these digits by swapping them.
The output is: 999984211
Algorithm
maxNum(number, swaps, maxNumber)
Input − The number as a string, the number of swaps and the maxNumber string.
Output − Update the maxNumber to get the largest value.
Begin
if swaps = 0, then
return
n := number of digits in the number
for i := 0 to n-2, do
for j := i+1 to n-1, do
if number[i] < number[j], then
exchange number[i] and number[j]
if number is greater than maxNumber, then
maxNumber := number
maxNum(number, swaps-1, maxNumber)
exchange number[i] and number[j] again for backtrack
done
done
End
Example
#include < iostream >
using namespace std;
void maxNum(string str, int swaps, string &max) {
if(swaps == 0) //when no swaps are left
return;
int n = str.length();
for (int i = 0; i < n - 1; i++) { //for every digits og given number
for (int j = i + 1; j < n; j++) {
if (str[i] < str[j]) { //when ith number smaller than jth number
swap(str[i], str[j]);
if (str.compare(max) > 0) //when current number is greater, make it
maximum
max = str;
maxNum(str, swaps - 1, max); //go for next swaps
swap(str[i], str[j]); //when it fails, reverse the swapping
}
}
}
}
int main() {
string str = "129814999";
int swapNumber = 4;
string max = str;
maxNum(str, swapNumber, max);
cout <<"The given number is: " << str << endl;
cout <<"The maximum number is: "<< max << endl;
}
Output
The given number is: 129814999
The maximum number is: 999984211