একটি প্রদত্ত স্ট্রিং এর সমস্ত স্থানান্তর মুদ্রণ করুন

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

উদাহরণস্বরূপ, যদি স্ট্রিংটি ABC হয়, তাহলে সমস্ত স্থানান্তর হবে ABC, ACB, BAC, BCA, CAB, CBA৷

এই অ্যালগরিদমের জটিলতা হল O(n!)। এটি একটি বিশাল জটিলতা। যখন স্ট্রিং আকার বৃদ্ধি পায়, তখন কাজটি শেষ করতে আরও বেশি সময় লাগে৷

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

Input:
A string “ABC”
Output:
All permutations of ABC is:
ABC
ACB
BAC
BCA
CBA
CAB

অ্যালগরিদম

stringPermutation(str, left, right)

ইনপুট: স্ট্রিং এবং অক্ষরগুলির বাম এবং ডান সূচক।

আউটপুট: স্ট্রিং এর সমস্ত স্থানান্তর প্রিন্ট করুন।

Begin
   if left = right, then
      display str
   else
      for i := left to right, do
         swap str[left] and str[i]
         stringPermutation(str, left+1, right)
         swap str[left] and str[i]             //for backtrack
      done
End

উদাহরণ

#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]); //swap back for backtracking
      }
   }
}

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