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