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

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

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

एल्गोरिदम

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 <iostream>
#include <algorithm>
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