Interview Question |Permutations Of A Given String| Recursion & Backtracking | C++

Interview Question |Permutations Of A Given String| Recursion & Backtracking | C++

Code :

void solve(int ind,string &s,vector<string>&ans)
     {
         if(ind==s.length())
         {
             ans.push_back(s);
             return;
         }
         for(int i=ind;i<s.length();i++)
         {
             if(i>ind && s[i]==s[i-1])continue;
             swap(s[i],s[ind]);
             solve(ind+1,s,ans);
             swap(s[i],s[ind]);
         }
     }
  vector<string>find_permutation(string s)
  {
      vector<string>ans;
      sort(s.begin(),s.end());
      solve(0,s,ans);
      sort(ans.begin(),ans.end());
      return ans;
  }

English :

This C++ code generates all permutations of a given string s without repetitions. The find_permutation function takes a string as input and returns a vector of strings containing all the unique permutations of the input string.

Here’s a step-by-step explanation of the code:

solve function:

• void solve(int ind, string &s, vector<string> &ans)

This recursive function generates permutations of the string s starting from the given index ind. The permutations are stored in the vector ans.

• If ind is equal to the length of the string s, it means a permutation is complete, so the current permutation is added to the ans vector.
• Otherwise, it iterates over the characters in the string starting from the current index ind. It uses recursion to generate permutations by swapping characters.
• Inside the loop, it checks whether the current character is the same as the previous one (i.e., s[i] == s[i-1]). If true, it continues to the next iteration to avoid duplicate permutations.
• It then swaps the characters at indices i and ind in the string s and calls the solve function recursively with an incremented index (ind + 1).
• After the recursive call, it swaps the characters back to restore the original state of the string.

find_permutation function:

• vector<string> find_permutation(string s)

This function initializes the process by first sorting the input string s and then calling the solve function with the initial index set to 0.

• Before calling solve, it sorts the characters in the string. Sorting helps to identify and skip duplicate characters during the permutation process.
• After generating all permutations, it sorts the resulting vector ans to ensure the permutations are in lexicographically sorted order.
• The sorted vector of permutations is then returned.

Here’s a simple example:

int main() {
    string input = "abc";
    vector<string> result = find_permutation(input);

    for (const string &perm : result) {
        cout << perm << " ";
    }
    return 0;
}

Output:

abc acb bac bca cab cba

This example demonstrates the generation of all unique permutations of the string “abc”.

Hindi :

यह C++ कोड एक दिए गए स्ट्रिंग s के सभी पुनरावर्तन बनाता है बिना दोहराए। find_permutation फ़ंक्शन एक स्ट्रिंग को इनपुट के रूप में लेता है और उसके सभी अद्वितीय पुनरावर्तनों को स्टोर करने वाले एक स्ट्रिंग के वेक्टर को वापसी देता है।

कोड का विस्तृत विवरण:

solve फ़ंक्शन:

• void solve(int ind, string &s, vector<string> &ans)

यह रेकर्सिव फ़ंक्शन s स्ट्रिंग से शुरू होकर दिए गए सूची में अनुसार स्ट्रिंग s के सभी अद्वितीय पुनरावर्तन बनाता है। पुनरावर्तन वेक्टर ans में स्टोर किए जाते हैं।

• यदि ind स्ट्रिंग s की लंबाई के बराबर है, तो यह यहाँ तक है कि एक पुनरावर्तन पूरा है, इसलिए वर्तमान पुनरावर्तन को ans वेक्टर में जोड़ा जाता है।
• अन्यथा, यह वर्तमान सूची में स्थित सूची के सभी अक्षरों पर लूप करता है जो ind से शुरू होता है। यह अक्षरों को बदलकर पुनरावर्तन बनाने के लिए रेकर्सन का उपयोग करता है।
• लूप के भीतर, यह यह जाँचता है कि वर्तमान वर्ण पिछले वर्ण के समान है या नहीं (अर्थात् s[i] == s[i-1])। यदि सत्य है, तो यह डुप्लिकेट पुनरावर्तन को टालने के लिए अगले यात्रा के लिए जारी रखता है।
• फिर यह सूची के स्थिति को बहाल करने के लिए वर्णों को स्वैप करता है और solve फ़ंक्शन को एक इंक्रीमेंट इंडेक्स के साथ ( ind + 1 ) रेकर्सिवली कॉल करता है।
• रेकर्सिव कॉल के बाद, यह वर्णों को पुनर्स्थापित करने के लिए उन्हें पुनर्स्थापित करता है।

find_permutation फ़ंक्शन:

• vector<string> find_permutation(string s)

यह प्रक्रिया को प्रारंभ करने के लिए पहले स्ट्रिंग s को क्रमबद्ध करता है और फिर इंडेक्स को 0 पर सेट करके solve फ़ंक्शन को कॉल करता है।

• solve को कॉल करने से पहले, यह स्ट्रिंग में वर्णों को क्रमबद्ध करता है। क्रमबद्ध करना यह सुनिश्चित करने में मदद करता है कि पुनरावर्तन प्रक्रिया के दौरान डुप्लिकेट वर्णों को पहचाना और छोड़ दिया जा सके।
• सभी पुनरावर्तनों को उत्पन्न करने के बाद, इसने परिणामक सूची ans को क्रमबद्ध करने के लिए उन्हें लिखा है ताकि पुनरावर्तनों को शब्दकोशिक क्रम में रखा जा सके।
• सॉर्ट किए गए पुनरावर्तनों का सॉर्ट किया गया वेक्टर फिर वापस किया जाता है।
• आयतनबद्ध सूची पुनर्विद्वेष करने के लिए लौटाई जाती है।

यहाँ एक सरल उदाहरण है:

int main() {
    string input = "abc";
    vector<string> result = find_permutation(input);

    for (const string &perm : result) {
        cout << perm << " ";
    }
    return 0;
}

आउटपुट:

abc acb bac bca cab cba

इस उदाहरण में “abc” स्ट्रिंग के सभी अद्वितीय पुनरावर्तनों का उत्पन्न होना दिखाया गया है।

Hinglish :

Yeh C++ code ek di gayi string s ke sare unique permutations banata hai bina repetition ke. find_permutation function ek string ko input ke roop mein leta hai aur ek vector of strings return karta hai jo input string ke saare unique permutations ko contain karta hai.

Yahaan code ki step-by-step samjhauta hai:

solve function:

• void solve(int ind, string &s, vector<string> &ans)

Yeh recursive function s string mein se diye gaye index ind se shuru hokar permutations banata hai. Permutations ans vector mein store hoti hain.

• Agar ind string s ke length ke barabar hai, toh yeh matlab hai ki ek permutation complete ho gayi hai, isliye current permutation ko ans vector mein add kar diya jata hai.
• Warna, yeh characters ko current index ind se shuru karke string mein iterate karta hai. Yeh characters ko swap karke permutations banane ke liye recursion ka istemal karta hai.
• Loop ke andar, yeh check karta hai ki kya current character pichle character ke samaan hai (i.e., s[i] == s[i-1]). Agar yeh sach hai, toh woh duplicate permutations ko avoid karne ke liye next iteration mein chala jata hai.
• Fir woh characters ko string s mein indices i aur ind par swap karta hai aur solve function ko recursion ke zariye ek badhaye gaye index ke saath (ind + 1) call karta hai.
• Recursion ke baad, woh characters ko phir se swap karta hai taki string ka original state restore ho sake.

find_permutation function:

• vector<string> find_permutation(string s)

Yeh function process ko initialize karta hai pehle string s ko sort karke aur fir solve function ko index ko 0 par set karke call karta hai.

• solve ko call karne se pehle, woh string ke characters ko sort karta hai. Sorting duplicate characters ko permutation process ke doran identify karne aur skip karne mein madad karta hai.
• Sare permutations banane ke baad, woh resulting vector ans ko sort karta hai taki permutations lexicographically sorted order mein ho.
• Sort kiya gaya vector permutations ko fir return kiya jata hai.

Yehan ek simple example hai:

int main() {
    string input = "abc";
    vector<string> result = find_permutation(input);

    for (const string &perm : result) {
        cout << perm << " ";
    }
    return 0;
}

Output:

abc acb bac bca cab cba

Is example mein “abc” string ke saare unique permutations banane ka process dikhaya gaya hai.

Question Link :

https://www.geeksforgeeks.org/problems/permutations-of-a-given-string2041/1?page=1&category=Recursion&sprint=94ade6723438d94ecf0c00c3937dad55&sortBy=submissions