I have written a code which gives all permutations of a string. I have
assumed that all the characters in a given string are distinct.
The main idea is as follows
-if suppose "abc" is given first
my base case is to form permutations of two characters
so I will have "ab" and "ba"
Now, I will just switch places of c - like "cab","acb" and "abc" - from the
string "ab"
Similarly obtain "cba","bca" and "bac" from "ba".
I have implemented this logic using recursion. The implementation is given
below
I would like to know is there is any other efficient ways to do this
#include<iostream>
#include<string>
#include<string.h>
#define SIZE 7
using namespace std;
string * permutations (char *array,string *stringarray,int len);
string * Join(string *stringarray,char append);
int factorial (int n);
int numpermutations;
main()
{
char array[]="bcad";
//Write a program to find the factorial of a number
numpermutations = factorial(strlen(array));
string *stringarray = new string[numpermutations];
int i;
for(i=0;i<numpermutations;i++)
stringarray[i] = "\0";
permutations(array,stringarray,strlen(array)-1);
i=0;
while(i!=numpermutations)
{
cout<<stringarray[i]<<endl;
i++;
}
}
int factorial (int n)
{
int fact;
if(n==2)
return 2;
else
{
fact = n*factorial(n-1);
return fact;
}
}
string *permutations(char *array,string *stringarray, int len)
{
string * tempstring;
if(len == 1)
{
char temp[3];
temp[0] = array[0];//Here I am doing the swapping
temp[1] = array[1];
temp[2] = '\0';
stringarray[0] = temp;
temp[0] = array[1];
temp[1] = array[0];
temp[2] = '\0';
stringarray[1] = temp;
int i;
}
else
{
stringarray =
Join(permutations(array,stringarray,len-1),array[len]);//using recursion
}
return stringarray;
}
string * Join(string *stringarray,char append)//This is to join string and
a character
{
int str_len = stringarray[0].length();//Get the length of one of the
strings
string tempstring[numpermutations];
int i;
for(i=0;i<numpermutations;i++)
tempstring[i] = "\0";
int j,temparrayindex=0;
i=0;
/* cout<<"First print wht is string array"<<stringarray[0]<<endl;
cout<<"stringarray[1]"<<stringarray[1]<<endl;*/
while(stringarray[i]!="\0")
{
char *temp = new char[str_len+1];
for(j=0;j<=str_len;j++)
{
int k;
for(k=0;k<j;k++)
temp[k] = stringarray[i][k];
temp[k] = append;
for(k=j+1;k<=str_len;k++)
temp[k] = stringarray[i][k-1];
temp[k]='\0';
tempstring[temparrayindex]=temp;
temparrayindex++;
}
delete []temp;
i++;
}
i=0;
while(i != numpermutations)
{
stringarray[i] = tempstring[i];
i++;
}
return stringarray;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/rSViVJl9Fu8J.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
