অদলবদল করে সর্বাধিক সংখ্যা

এই সমস্যায়, একটি ধনাত্মক পূর্ণসংখ্যার স্ট্রিং দেওয়া হয়েছে, আমাদেরকে বিভিন্ন জায়গায় 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)

ইনপুট - একটি স্ট্রিং হিসাবে সংখ্যা, অদলবদল সংখ্যা এবং maxNumber স্ট্রিং।

আউটপুট - সবচেয়ে বড় মান পেতে 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