All permutations of a string using iteration?

In this section we will see how to get all permutations of a string. The recursive approach is very simple. It uses the back-tracking procedure. But here we will use the iterative approach.

All permutations of a string ABC are like {ABC, ACB, BAC, BCA, CAB, CBA}. Let us see the algorithm to get the better idea.

Algorithm

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

Example

 Live Demo

#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); }

Output

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