C++ Code: Detemine combinations of String by using STL

/*Combinations of String */


#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<set>
#include<algorithm>

using namespace std;

typedef vector<string> vec_str;
typedef map<int,vec_str> map_vec_str;

bool mysort(string str1,string str2)
{
return str1.size()<str2.size();
}
void calculation(string str,map_vec_str &res_map)
{
int i,j,length,len,vl,sl;
string temp;
char ch;
length=str.size();
length--;
for(i=0;i<=length;i++)
{
temp="";
temp.insert(0,1,str[i]);
res_map[i].push_back(temp);
}
len=1;
vec_str vec;
while(len<=length)
{
ch=str[len];
for(i=0;i<len;i++)
{
vec=res_map[i];
vl=vec.size();
for(j=0;j<vl;j++)
{
temp=vec[j];
sl=temp.size();
temp.insert(sl,1,ch);
res_map[i].push_back(temp);
}
}
len++;
}
}

void combination(string str,vec_str &res_vec)
{
int i,j,mlen,vlen;
vec_str vec;
map_vec_str mymap;
set<string> st;
set<string>::iterator it;
calculation(str,mymap);
mlen=mymap.size();
for(i=0;i<mlen;i++)
{
vec=mymap[i];
vlen=vec.size();
for(j=0;j<vlen;j++)
st.insert(vec[j]);
}
for(it=st.begin();it!=st.end();it++)
res_vec.push_back(*it);
sort(res_vec.begin(),res_vec.end(),mysort);
}

void combination(string str,int r,vec_str &res_vec)
{
int i,j,mlen,vlen;
vec_str vec;
map_vec_str mymap;
set<string> st;
set<string>::iterator it;
calculation(str,mymap);
mlen=mymap.size();
for(i=0;i<mlen;i++)
{
vec=mymap[i];
vlen=vec.size();
for(j=0;j<vlen;j++)
{
if(vec[j].size()==r)
st.insert(vec[j]);
}
}
for(it=st.begin();it!=st.end();it++)
res_vec.push_back(*it);
}

int main()
{
vec_str ans_vec;
string str;
str="abaca";
cout<<"Determine all combination from 1 to string length size.."<<endl;
combination(str,ans_vec);
for(int i=0;i<ans_vec.size();i++)
cout<<ans_vec[i]<<endl;
ans_vec.clear();
cout<<endl<<"Determine r size combination from string.. For example: r is 3"<<endl; 
combination(str,3,ans_vec);
for(int i=0;i<ans_vec.size();i++)
cout<<ans_vec[i]<<endl;
return 0;
}


Output:

Determine all combination from 1 to string length size..
a
b
c
aa
ab
ac
ba
bc
ca
aaa
aac
aba
abc
aca
baa
bac
bca
aaca
abaa
abac
abca
baca
abaca

Determine r size combination from string.. For example: r is 3
aaa
aac
aba
abc
aca
baa
bac
bca

Comments

Post a Comment

Popular posts from this blog

uva 679 - Dropping Balls Solution

uva 679 - Dropping Balls Solution Algorithm: 1. convert (position-1)  to binary and store it to a string. 2. make the binary string length equal to the (depth-1) by adding zero(0) at start of the string. 3. reverse the binary string. 4. convert binary string to integer + power(2,depth-1). Example: depth=7; position=4; covert 4-1= 3 to binary. binary string is 11. make the string length 7-1=6 by adding 0. Updated string 000011. reverse the binary string and string is now 110000 convert binary string(110000) to integer. value is 48. calculate power_value=pow(2,7-1)=pow(2,6)=64. Answer is = 48 + 64=112. Code in C++: #include<iostream> #include<string> #include<algorithm> using namespace std; string convertDecimalToBinary(int num){ string result; while(num!=0){ if(num%2==1) result.insert(0,1,'1'); else result.insert(0,1,'0'); num=num/2; } return result; } int convertBinaryToDecimal(string &n...
Read more

uva 481 - What Goes Up Solution

uva 481 - What Goes Up Solution #include<iostream> #include<vector> using namespace std; void binary_search(int *arr, int search_value, int start, int end, int &index){ if (start == end){ index = start; return; } int mid = (start + end) / 2; if (arr[mid] == search_value){ index = mid; return; } else if (arr[mid + 1] == search_value){ index = mid + 1; return; } else if (arr[mid]<search_value && arr[mid + 1]>search_value){ index = mid + 1; return; } else if (arr[mid] > search_value){ binary_search(arr, search_value, start, mid, index); } else{ binary_search(arr, search_value, mid + 1, end, index); } } void calculate_lis(vector<int>&arr,vector<int>&result){ int *temp, i, max = 0, j, index, n = arr.size(), *res; temp = new int[n]; res = new int[n]; temp[0] = 0; for (i = 1; i < n; i++){ if (arr[temp[max]] < arr[i]){ res[i] = temp[max]; max++; ...
Read more

uva-10077 Solution --- The Stern-Brocot Number System

#include<iostream> using namespace std; int main(){ int input_num,input_den,left_num,left_den,right_num,right_den,cur_num,cur_den; while(cin>>input_num>>input_den){ if(input_num==1 && input_den==1) break; left_num=0; left_den=1; right_num=1; right_den=0; cur_num=cur_den=1; while(true){ if(cur_num== input_num && cur_den==input_den) break; if(cur_num*input_den < cur_den*input_num){ cout<<"R"; left_num=cur_num; left_den=cur_den; cur_num+=right_num; cur_den+=right_den; }else{ cout<<"L"; right_num=cur_num; right_den=cur_den; cur_num+=left_num; cur_den+=left_den; } } cout<<endl; } return 0; }
Read more