Python Program to find Maximum number possible by doing at-most K swaps

In this tutorial, we will see how to find the maximum number possible by doing at most K swaps in the number in Python.
Consider the following examples:

INPUT: Number=189 K=1
OUTPUT: 981
EXPLANATION: 1 is swapped with 9

INPUT: Number=198 K=2
OUTPUT: 981
EXPLANATION:
Swap 9 with 1 so the number becomes 918.
981 is the output after swapping 8 with 1.

INPUT: Number=98765 K=1
OUTPUT: 98765
EXPLANATION: No swap requirement. 

INPUT: Number=139714999, K = 4
OUTPUT: 999974211
EXPLANATION:
Swap 9 with 1 so number becomes 939714991
Swap 9 with 3 so number becomes 999714391
Swap 9 with 7 so number becomes 999914371
Swap 1 with 7 so number becomes 999974311

 

Find Maximum number possible by doing at-most K swaps in Python

In this program, we consider every digit and swap it with the following digits and check if it produces the maximum number. The function is called recursively K times.

#Strings are immutable.
#Therefore returning a new string with swapped values
def swap(string, i, j): 
  return (string[:i] + string[j] + string[i + 1:j] + string[i] + string[j + 1:]) 

#Recursive function 
def Afterkswap(string, k, maxm): 
  # return if no swaps left 
  if k == 0: 
    return
  n = len(string) 
  for i in range(n - 1): 
    for j in range(i + 1, n): 
      if string[i] < string[j]: 
        string = swap(string, i, j) 
        #if the returned string is greater than the current number
        if string > maxm[0]: 
          maxm[0] = string 
        #Recursively call findMaximumNum  
        Afterkswap(string, k - 1, maxm) 
        # backtrack 
        string = swap(string, i, j) 

# Driver Code 
s= "645957321"
k = 5
maxm = [s] 
Afterkswap(string, k, maxm) 
print("Greatest Number after K swaps:",maxm[0]) 

OUTPUT

Greatest Number after k swaps: 976554321

Hope you liked this tutorial!
Also read:

How to swap two numbers without using third variable in Python

How to find the number of zeros in Python

Leave a Reply

Your email address will not be published. Required fields are marked *