String Permutation Using STL C++ and Print Lexicographic order


/* String Permutation Using STL C++ and Print Lexicographic order
    using next_permutation function.
*/
#include<iostream>
#include <set>
#include <string>
#include<string.h>
#include<algorithm>
#define MAX_SIZE 100
using namespace std;

int main ()
{
    string str,temp;
    set<string> myset;
    char ch[MAX_SIZE];
    int i,j,len;
    cin>>str;
    len=str.size();
    strcpy(ch,str.c_str());
    sort(ch,ch+len);
    str=ch;
    for(i=0;i<len;i++)
    {
        for(j=1;j<=len-i;j++)
        {
            temp=str.substr(i,j);
            strcpy(ch,temp.c_str());
            do
            {
                myset.insert(ch);
            }while(next_permutation(ch,ch+j));
        }
    }
    set<string>::iterator it;
    for(it=myset.begin();it!=myset.end();it++)
        cout<<*it<<endl;
    return 0;
}

Input: 
           bacda
Output:
  a
aa
aab
aabc
aabcd
aabdc
aacb
aacbd
aacdb
aadbc
aadcb
ab
aba
abac
abacd
abadc
abc
abca
abcad
abcd
abcda
abdac
abdc
abdca
acab
acabd
acadb
acb
acba
acbad
acbd
acbda
acdab
acdb
acdba
adabc
adacb
adbac
adbc
adbca
adcab
adcb
adcba
b
ba
baa
baac
baacd
baadc
bac
baca
bacad
bacd
bacda
badac
badc
badca
bc
bca
bcaa
bcaad
bcad
bcada
bcd
bcda
bcdaa
bdaac
bdac
bdaca
bdc
bdca
bdcaa
c
caab
caabd
caadb
cab
caba
cabad
cabd
cabda
cadab
cadb
cadba
cb
cba
cbaa
cbaad
cbad
cbada
cbd
cbda
cbdaa
cd
cdaab
cdab
cdaba
cdb
cdba
cdbaa
d
daabc
daacb
dabac
dabc
dabca
dacab
dacb
dacba
dbaac
dbac
dbaca
dbc
dbca
dbcaa
dc
dcaab
dcab
dcaba
dcb
dcba
dcbaa


Input:
    aaa
Output:
  a
  aa
  aaa

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