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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.