Wednesday, March 19, 2014

Find all permutations of string

Given string s, find all permutations of it. Don't worry about repeating.
E.g.: "hat" should give o/p:
“tha”, “aht”, “tah”, “ath”, “hta”, and “hat"

E.g.  "aaa" should give o/p aaa 6 times

-Note that repetition can be simply avoided by using a hashmap to quickly check if that permutation has been counted or not

C++ prog:

#include <iostream>
#include <map>
#include <vector>
#include <tr1/unordered_map>
#include <tr1/unordered_set>

using namespace std;
using namespace tr1;

void printVec(vector<string> v){
int i = 0;
cout << "start printing vec: "<< endl;
while(i < v.size()){
//cout << "i: " << i << endl;
cout  << v[i] << endl;
i++;
}
cout << "stop printing vec, i: " << i << endl;
return;
}


vector<string> perms(string s){
//cout << "input string: " << s << endl;
string temp;
vector<string> v (0);
if(s.length() <= 0){
//cout << "input string blank: " << s << endl;
temp = "";
v.push_back(temp);
//cout << "return vector: " << endl;
//printVec(v);
return v;
}
char c;
int i = 0; int j = 0;
vector<string> ret_vec (0);
string temp1;

c = s[0];
temp = s.substr(1, (s.length()-1));
ret_vec = perms(temp);

while(i < ret_vec.size()){
temp = ret_vec[i];
//cout << "======================================="<< endl;
//cout << "i: " << i << "  temp: " << temp << endl;
j = 0;

while(j <= temp.size()){
temp1 = temp;
temp1.insert(j, 1, c);
//cout << "j: " << i << "  temp1: " << temp1 << endl;
v.push_back(temp1);
j++;
}
i++;
}
//cout << "final return vector: " << endl;
//printVec(v);
return v;
}


int main (int argc, char * const argv[]) {
string s = "aaa";
vector<string> v (0);
v = perms(s);
printVec(v);
    return 0;
}

No comments:

Post a Comment