स्वैप करके अधिकतम संख्या

इस समस्या में, एक धनात्मक पूर्णांक स्ट्रिंग दी गई है, हमें विभिन्न स्थानों में अंकों के k बार की अदला-बदली करके क्रमपरिवर्तन का पता लगाना है जिसका मान अधिकतम है।

हम इस समस्या को एक अंक चुनकर हल करेंगे और अधिकतम संख्या खोजने के लिए इसे एक बार में एक के बाद के अंकों के साथ स्वैप करेंगे। हम प्रक्रिया को k बार दोहराते हैं। बैकट्रैकिंग रणनीति यहां काम कर रही है क्योंकि जब हमें कोई संख्या मिलती है जो पिछले मान से अधिक नहीं है, तो हम पुराने मान पर वापस जाते हैं और फिर से जांचते हैं।

इनपुट और आउटपुट

Input:
A number of multiple digits.
The input is: 129814999
Output:
The maximum value from these digits by swapping them.
The output is: 999984211

एल्गोरिदम

maxNum(number, swaps, maxNumber)

इनपुट - एक स्ट्रिंग के रूप में संख्या, स्वैप की संख्या और अधिकतम संख्या स्ट्रिंग।

आउटपुट - सबसे बड़ा मान प्राप्त करने के लिए अधिकतम संख्या अपडेट करें।

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

उदाहरण

#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;
}

आउटपुट

The given number is: 129814999
The maximum number is: 999984211