किसी दिए गए स्ट्रिंग के सभी क्रमपरिवर्तन प्रिंट करें

किसी दिए गए स्ट्रिंग के सभी क्रमपरिवर्तन को प्रिंट करना बैकट्रैकिंग समस्या का एक उदाहरण है। हम उप-समस्याओं को हल करने के लिए सबस्ट्रिंग के आकार को कम कर देंगे, फिर उस खंड से एक और क्रमपरिवर्तन प्राप्त करने के लिए फिर से पीछे हटेंगे।

उदाहरण के लिए, यदि स्ट्रिंग एबीसी है, तो सभी क्रमपरिवर्तन एबीसी, एसीबी, बीएसी, बीसीए, सीएबी, सीबीए होंगे।

इस एल्गोरिथ्म की जटिलता हे (एन!) यह एक बड़ी जटिलता है। जब स्ट्रिंग का आकार बढ़ता है, तो कार्य को पूरा करने में अधिक समय लगता है।

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

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