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

परिचय

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

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

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

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

इनपुट: एक स्ट्रिंग "ABC"
आउटपुट: ABC के सभी क्रमपरिवर्तन हैं: ABC ACB BAC BCA CBA CAB

एल्गोरिदम

stringPermutation(str, left, right)
इनपुट: स्ट्रिंग और वर्णों के बाएं और दाएं इंडेक्स
आउटपुट: स्ट्रिंग के सभी क्रमपरिवर्तन प्रिंट करें

Begin
    यदि left = right, तो
        str प्रदर्शित करें
    अन्यथा
        i := left से right तक, करें
            str[left] और str[i] को स्वैप करें
            stringPermutation(str, left+1, right)
            str[left] और str[i] को स्वैप करें
            // बैकट्रैक के लिए
        done
End

उदाहरण (C++ कोड)

#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