স್ವ্যাপিং দিয়ে সর্বোচ্চ সংখ্যা নির্ণয়

ভূমিকা

এই সমস্যায়, একটি ধনাত্মক পূর্ণসংখ্যা স্ট্রিং দেওয়া আছে, আমাদেরকে কে স্ব্যাপিং দিয়ে k বার ডিজিটগুলো বিভিন্ন জায়গায় বদলিয়ে যেই পারমুটেশনের মান সর্বোচ্চ হবে তা বের করতে হবে।

এই সমস্যাটি আমরা একটি ডিজিট বেছে নেওয়া এবং এর পরে আসা ডিজিটগুলোর সাথে একে একে বদলিয়ে সর্বোচ্চ সংখ্যা খুঁজে বের করে সমাধান করব। এই প্রক্রিয়াটি k বার दुहरাব। ব্যাকট্র্যাকিং কৌশল এখানে কাজ করছে কারণ যখন আমরা একটি সংখ্যা পাই যা পূর্বের মান থেকে বড় নয়, তখন আমরা পুরনো মানে ফিরে যাই (ব্যাকট্র্যাক) এবং আবার চেক করি।

ইনপুট এবং আউটপুট

ইনপুট: একাধিক ডিজিটের একটি সংখ্যা। ইনপুট হলো: 129814999
আউটপুট: এই ডিজিটগুলোর থেকে স্ব্যাপিং দিয়ে সর্বোচ্চ মান। আউটপুট হলো: 999984211

অ্যালগরিদম

maxNum(number, swaps, maxNumber)

ইনপুট − সংখ্যাটি স্ট্রিং হিসেবে, স্ব্যাপের সংখ্যা এবং maxNumber স্ট্রিং।

আউটপুট − সর্বোচ্চ মান পাওয়ার জন্য maxNumber আপডেট করা।

শুরু
    যদি swaps = 0 হয়, তবে
        ফিরে যাও
    n := সংখ্যাটিতে ডিজিটের সংখ্যা
    i := 0 থেকে n-2 পর্যন্ত, করো
        j := i+1 থেকে n-1 পর্যন্ত, করো
            যদি number[i] < number[j], তবে
                number[i] এবং number[j] বদলাও
                যদি number > maxNumber হয়, তবে
                    maxNumber := number
                maxNum(number, swaps-1, maxNumber)
                ব্যাকট্র্যাকের জন্য আবার number[i] এবং number[j] বদলাও
            শেষ
        শেষ
    শেষ
শেষ

উদাহরণ (C++)

#include <iostream> 
using namespace std; 

void maxNum(string str, int swaps, string &max) { 
    if(swaps == 0) 
        //যখন কোনো স্ব্যাপ বাকি নেই
        return; 
    int n = str.length(); 
    for (int i = 0; i < n - 1; i++) { 
        //দেওয়া সংখ্যার প্রতিটি ডিজিটের জন্য
        for (int j = i + 1; j < n; j++) { 
            if (str[i] < str[j]) { 
                //যখন i-তম সংখ্যা j-তম সংখ্যা থেকে ছোট
                swap(str[i], str[j]); 
                if (str.compare(max) > 0) 
                    //যখন বর্তমান সংখ্যা বড়, তখন এটি সর্বোচ্চ করো
                    max = str; 
                maxNum(str, swaps - 1, max); 
                //পরবর্তী স্ব্যাপের জন্য যাও
                swap(str[i], str[j]); 
                //যখন ব্যর্থ হয়, স্ব্যাপিং উল্টাও
            } 
        } 
    } 
} 

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