पुनरावृत्ति का उपयोग करके स्ट्रिंग के सभी क्रमपरिवर्तन

इस खंड में हम देखेंगे कि स्ट्रिंग के सभी क्रमपरिवर्तन कैसे प्राप्त करें। पुनरावर्ती दृष्टिकोण बहुत सरल है। यह बैक-ट्रैकिंग प्रक्रिया का उपयोग करता है। लेकिन यहां हम पुनरावृत्त दृष्टिकोण का उपयोग करेंगे।

स्ट्रिंग ABC के सभी क्रमपरिवर्तन {ABC, ACB, BAC, BCA, CAB, CBA} जैसे हैं। आइए एल्गोरिदम देखें ताकि बेहतर विचार मिल सके।

एल्गोरिदम

getAllPerm(str)

begin   sort the characters of the string   while true, do     print the string str     i := length of str – 1     while str[i - 1] >= str[i], do         i := i – 1         if i is 0, then             return         end if     done     j := length of str – 1     while j > i AND str[j] <= str[i – 1], do         j := j – 1     done     exchange the characters from position str[i - 1], str[j]     reverse the string.   done end

उदाहरण

#include  #include  using namespace std; void getAllPerm(string str){     sort(str.begin(), str.end());     while (true){         cout << str << endl;         int i = str.length() - 1;         while (str[i-1] >= str[i]){             if (--i == 0)             return;         }         int j = str.length() - 1;         while (j > i && str[j] <= str[i - 1])             j--;         swap(str[i - 1], str[j]);         reverse (str.begin() + i, str.end());     } } int main(){     string str = "WXYZ";     getAllPerm(str); }

आउटपुट

WXYZ WXZY WYXZ WYZX WZXY WZYX XWYZ XWZY XYWZ XYZW XZWY XZYW YWXZ YWZX YXWZ YXZW YZWX YZXW ZWXY ZWYX ZXWY ZXYW ZYWX ZYXW