Friday, November 21, 2008

permutation of letters, including repetition

#include
#include
using namespace std;
int count=0,top=0;
char tempstr[50][50],a_ll_combinations[1000][15];
int checkEquality(char variable,char checking_string[50],int end,int i);
void permutation(int n,char string[50]);
int main()
{ ::count=0;
char string[50];
cout<<"Enter the string\n";
cin>>string;
cout<<"\n\nHere is all the possible combination of string "< int n=strlen(string); //calculating the string length
if (n==1)
{
cout<<"The only possible combination is \n";
cout< }
permutation(n,string); //calling the function
int i=1;
for (int i=0;i {
cout< }
cout<<"The number of combinations printed is "<<::count<<"\n";
return 0;
}
void permutation(int n,char string[50])
{
if(n==2)
{
//setting the base case as a small string of size 2
strcpy(a_ll_combinations[::top++],string); //so in the base case two strings are generated
if (string[1]==string[0])
{
::count++;
return;
}
char temp=string[0];
string[0]=string[1];
string[1]=temp;
strcpy(a_ll_combinations[::top++],string);
::count+=2;
return;
}
for (int i=0;i {
if (i==0)
{
strcpy(tempstr[n],string); //this is for saving the string that is passed for an element being at the last position recursively,
} //so that in the next state alteration can be done with the previous one
strcpy(string,tempstr[n]);
if(checkEquality(string[i],string,n,i)==1) //here it checks whether the character which is going to be swapped was already in the nth position
continue;
char temp=string[n-1]; //here, changing the last element in each iteration
string[n-1]=string[i];
string[i]=temp;
permutation(n-1,string); //calling for the permutation of n-1 letters -recursion

}
}
int checkEquality(char variable,char checking_string[50],int n,int end) //this is the definition for the checking for duplication
{
for (int i=0;i {
if (checking_string[i]==variable)
return 1;
}
return 0;
}

No comments: