Max Number By Swapping
What is Max number by Swapping Problem?
In the Max number by Swapping problem, there is a string containing numerical digits and a positive number 'k' is given and our task is to find the permutation whose value is maximum by swapping digits of given string 'k' times, into different places. For instance, if the given string N = 1739 and k = 1, then the maximum number that can be built is 9731.
Backtracking Approach
Let us look the Backtracking Approach to solve Max Number By Swapping Problem. Suppose the given string is −
Input: 129814999
The maximum value from these digits by swapping them could be −
Output: 999984211
The idea behind backtracking approach is to try all possible swaps of two digits in the given string 'N' and keep track of the maximum number obtained so far. Along with maximum number, we also need to keep track of how many swaps we have performed and stop when we reach 'k'.
To implement the backtracking approach, we need a main function and a helper function that will perform the following actions −
If the current number of swaps is equal to the maximum number of swaps, compare the current number with the current maximum number and update the maximum number if needed. Then return.
Loop through all pairs of digits in the current number. For each pair, swap them and call the helper function recursively.
After the recursive call, swap them back to restore the original number.
Pseudocode
Following is the pseudocode for solving max number by swapping problem using the backtracking approach −
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
The following example demonstrates how to solve the max number by swapping problem using backtracking approach in various programming languages.
#include <stdio.h>
#include <string.h>
void swap(char *x, char *y) {
char temp;
temp = *x;
*x = *y;
*y = temp;
}
void mxmNumbr(char str[], int swaps, char max[]) {
//when no swaps are left
if(swaps == 0)
return;
int n = strlen(str);
//for every digits of given number
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
//when ith number smaller than jth number
if (str[i] < str[j]) {
swap(&str[i], &str[j]);
//when current number is greater, make it maximum
if (strcmp(str, max) > 0)
strcpy(max, str);
//go for next swaps
mxmNumbr(str, swaps - 1, max);
//when it fails, reverse the swapping
swap(&str[i], &str[j]);
}
}
}
}
int main() {
char str[] = "129814999";
int swpNumbr = 4;
char max[10];
strcpy(max, str);
mxmNumbr(str, swpNumbr, max);
printf("The given number is: %s
", str);
printf("The maximum number is: %s
", max);
return 0;
}
#include <iostream>
using namespace std;
void mxmNumbr(string str, int swaps, string &max) {
//when no swaps are left
if(swaps == 0)
return;
int n = str.length();
//for every digits og given number
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
//when ith number smaller than jth number
if (str[i] < str[j]) {
swap(str[i], str[j]);
//when current number is greater, make it maximum
if (str.compare(max) > 0)
max = str;
//go for next swaps
mxmNumbr(str, swaps - 1, max);
//when it fails, reverse the swapping
swap(str[i], str[j]);
}
}
}
}
int main() {
string str = "129814999";
int swpNumbr = 4;
string max = str;
mxmNumbr(str, swpNumbr, max);
cout <<"The given number is: " <<str << endl;
cout <<"The maximum number is: "<< max << endl;
}
import java.util.*;
public class Main {
// Function to find maximum number after k swaps
static void mxmNumbr(StringBuilder str, int swaps, StringBuilder max) {
// when no swaps are left
if (swaps == 0)
return;
int n = str.length();
// for every digits of given number
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// when ith number smaller than jth number
if (str.charAt(i) < str.charAt(j)) {
// swap str[i] with str[j]
char temp = str.charAt(i);
str.setCharAt(i, str.charAt(j));
str.setCharAt(j, temp);
// when current number is greater, make it maximum
if (str.toString().compareTo(max.toString()) > 0)
max.replace(0, max.length(), str.toString());
// go for next swaps
mxmNumbr(str, swaps - 1, max);
// when it fails, reverse the swapping
temp = str.charAt(i);
str.setCharAt(i, str.charAt(j));
str.setCharAt(j, temp);
}
}
}
}
public static void main(String[] args) {
StringBuilder str = new StringBuilder("129814999");
int swpNumbr = 4;
StringBuilder max = new StringBuilder(str);
mxmNumbr(str, swpNumbr, max);
System.out.println("The given number is: " + str);
System.out.println("The maximum number is: " + max);
}
}
def mxmNumbr(str, swaps, max):
# when no swaps are left
if swaps == 0:
return
n = len(str)
# for every digits of given number
for i in range(n - 1):
for j in range(i + 1, n):
# when ith number smaller than jth number
if str[i] < str[j]:
# swap str[i] with str[j]
str[i], str[j] = str[j], str[i]
# when current number is greater, make it maximum
if str > max[0]:
max[0] = str[:]
# go for next swaps
mxmNumbr(str, swaps - 1, max)
# when it fails, reverse the swapping
str[i], str[j] = str[j], str[i]
def main():
str = list("129814999")
swpNumbr = 4
max = [str[:]]
mxmNumbr(str, swpNumbr, max)
print("The given number is: ", ''.join(str))
print("The maximum number is: ", ''.join(max[0]))
if __name__ == "__main__":
main()
Output
The given number is: 129814999 The maximum number is: 999984211
