c++ code to print possibities of a word without repetition

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

In my previous post i have written a program which prints all permutations of a word.. But i end up with a problem..

consider the input is abc.. Output will be

abc
acb
bac
bca
cab
cba

yeah.. it’s fine.. but now input is aba

aba
aab
baa
aab
aba

we can see the repetition of words.. To avoid that i have used a list which stores all the words and prints only the unique possibilities.

 

#include “iostream”
#include “string”
#include “list”

using namespace std;

void permute(string,int,int);
void store_to_list(string);
void swap(string&,int,int);
void rotate_left(string&,int,int);
string word;
list mylist;
list::iterator it;
int main()
{
cout<>word;
int len=word.length();
permute(word,0,len);
cout<<“\n\n”;
mylist.sort();
mylist.unique();
for( it = mylist.begin() ; it != mylist.end() ; it++ )
{
cout<<*it<<endl;
}
cin.get();
cin.get();
return 0;
}

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)
{
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;

}

 

Now for the same input aba output will be

aab
aba
baa

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