Printing Every Combination of a word

Posted: July 4, 2012 in Programming
Tags: , , , , ,

In past 2 posts we printed all the premutations and possiblities of a word.. Now i am trying to print every combination letter by letter..

For example the input abc will produce
a
ab
ba
abc
acb
bac
bca
cab
cba

To achieve this i have done only few changes in the previous program..

1. I have used vector instead of list since it is much difficult to remove duplicate strings in list
2. I have added a loop which will pass string to perform permutation..

For loop in the main function will increase the word length 1 by 1.. for example if the input is abcd.. first the permutation of a will be done. then for ab.. then abc.. so on..

In the store_to_list function i have created an iterator which will iterate through the vector content. if the word is not present it will push it to the vector else it will be ignored.. These 2 lines will be very helpful to avoid duplication of words in the list.

[sourcecode language=”cpp”]

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

void permute(string,int,int);
void store_to_list(string);
void swap(string&,int,int);
void rotate_left(string&,int,int);
void print_list();
string word;
vector mylist;
vector::iterator it;
vector::iterator itemIterator;
int main()
{
cout<>word;
for(int i=0;i<=word.length();i++)
{
string nw=word.substr(0,i);
permute(nw,0,nw.length());
}
print_list();
return 0;
}

void print_list()
{
for( it = mylist.begin() ; it != mylist.end() ; it++ )
{
cout<<*it<<endl;
}

cin.get();
cin.get();
}

void permute(string w, int start, int n)
{
store_to_list(w);
if(start=start;i–)
{
for(j=i+1;j<n;j++)
{
swap(w,i,j);
permute(w,i+1,n);
}

rotate_left(w,i,n);

}
}

}

void store_to_list(string w)
{
itemIterator=find(mylist.begin(),mylist.end(),w);
if(itemIterator == mylist.end())
{
mylist.push_back(w);
}
}

void swap(string &w,int i,int j)
{
char t;
t=w[i];
w[i]=w[j];
w[j]=t;
}

void rotate_left(string &w,int go,int n)
{
char tmp=w[go];
for(int i=go;i<n-1;i++)
{
w[i]=w[i+1];
}
w[n-1]=tmp;

}


[/sourcecode]

Output:

Enter a string : abcd

a
ab
ba
abc
acb
bac
bca
cab
cba
abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s