permute.cc

// Compiled with: g++ -Wall -std=c++14 -pthread

#include <iostream>
#include <vector>
#include <map>

using namespace std;

//print array
void print(int* arr, int n) {
  vector<int> w_ (arr, arr+ n);
  for (auto i : w_) {
    cout << i << " ";
  }
  
  cout << endl;
}

void permute(int a[], int i, int n)
{
   int j;
   //cout << "permute " << i << endl;
   //print entire string when we reach the end
   if (i == n) {
     print(a, n);
   } else {
       for (j = i; j < n; j++)
       {
          swap(a[i], a[j]);
         // cout << "swap i = " << i << " j = " << j << endl;
          permute(a, i+1, n);
          swap(a[i], a[j]);
         
       }
        //  cout << "exit " << i << endl;
   }
} 


map<char, vector<char>> password_map = {{ 'a' , {'1', '2', '3'}}, {'l', {'L'}},  {'e', {'x', 'y'}  }};
 
void permute_string(string s, int i, int n) {
    if (i == n) {
      cout << s << endl;
      return;
    }
    
    bool permuted = false;
    int j = i;
    for (j = i; j < n; j++) {
        if (password_map.find(s[j]) != password_map.end()) {
            auto vec = password_map[s[j]];
            permuted = true;
            permute_string(s, j + 1, s.size());
            for (size_t k = 0; k < vec.size(); k++) {
                char temp = s[j];
                s[j] = vec[k];
                permute_string(s, j + 1, s.size());
                //backtrack
                s[j] = temp;
            }
            return;
        }
    }
   
    if (!permuted) {
        permute_string(s, n, n);
    }
}


int main(){
    string str = "apple";
    permute_string(str, 0, 5); 
   // int arr[] = { 1, 2, 3};
   // permute(arr, 0, 3);