Johnson trotter algorithm is another way to generate all permutations......
On Saturday, May 5, 2012 4:08:13 PM UTC+5:30, Sairam wrote:
>
> 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;
>
> }
>
On Saturday, May 5, 2012 4:08:13 PM UTC+5:30, Sairam wrote:
>
> 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/-/oXf35kSrZ9YJ.
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.
