স্ট্রিংয়ের সকল পারমুটেশন প্রিন্ট (Print all permutations of a given string)

একটি প্রদত্ত স্ট্রিংয়ের সকল পারমুটেশন প্রিন্ট করা একটি ব্যাকট্র্যাকিং সমস্যার উদাহরণ। আমরা সাবস্ট্রিংয়ের আকার কমানো সাব-প্রব্লেম সমাধান করব, তারপর আবার ব্যাকট্র্যাক করে ঐ সেকশন থেকে অন্য পারমুটেশন পাব।

উদাহরণস্বরূপ, স্ট্রিং ABC হলে, সব পারমুটেশন হবে ABC, ACB, BAC, BCA, CAB, CBA।

এই অ্যালগরিদমের জটিলতা O(n!)。 এটি অনেক বড় জটিলতা। স্ট্রিংয়ের আকার বেড়ালে, টাস্ক ফিনিশ করতে বেশি সময় লাগবে।

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

ইনপুট: একটি স্ট্রিং "ABC" আউটপুট: ABC-এর সকল পারমুটেশন: ABC ACB BAC BCA CBA CAB

অ্যালগরিদম

stringPermutation(str, left, right)

ইনপুট: স্ট্রিং এবং ক্যারেক্টারের লেফট এবং রাইট ইনডেক্স।

আউটপুট: স্ট্রিংয়ের সকল পারমুটেশন প্রিন্ট করুন।

শুরু 
  যদি left = right, তবে 
    str প্রদর্শন করুন 
  অন্যথায় 
    i := left থেকে right পর্যন্ত, করুন 
      str[left] এবং str[i] সোয়াপ করুন 
      stringPermutation(str, left+1, right) 
      str[left] এবং str[i] সোয়াপ করুন 
        //ব্যাকট্র্যাক করার জন্য 
    শেষ 
শেষ

উদাহরণ

#include<iostream> using namespace std; void stringPermutation(string str, int left, int right) {   if(left == right)     cout << str << endl;   else {     for(int i = left; i<= right; i++) {       swap(str[left], str[i]);       stringPermutation(str, left + 1, right);       swap(str[left], str[i]); //ব্যাকট্র্যাকিংয়ের জন্য আবার সোয়াপ   }   } } int main() {   string str = "ABC";   cout << "All permutations of " << str << " is: " <<endl<<endl;   stringPermutation(str, 0, str.size()-1); } 

আউটপুট

All permutations of ABC is: ABC ACB BAC BCA CBA CAB