Permutation of String and Numbers in C++
A permutation is a mathematical concept in which it gives the total number of ways a set can be arranged.
A set can be of numbers or characters. I had made this project on permutation in which not only it will print the total number of ways but also print all the arrangements also.
In this project, you will be asked to give your name and then it will print all the possible arrangements of your name and also print the total number of ways. I had used the concept of recursion and also used the pointers.
I had made two methods in this program one is two swap the characters passed and other is the recursive method.
In swap() method, it takes two parameters both are pointers to a character whose values are swapped latter and to reflect this change on the actual parameters we used pointers which help to use the call by reference concept.
1 2 3 4 5 6 7 | void swap(char *a, char *b){ char temp = *a; *a = *b; *b = temp; } |
Another method which is used is permute() which is a recursive method. The base case just prints the string and the recursive case firstly gives the characters to the swap method which swap the characters in the actual string then it gives the string and the position to the recursive method.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | void permute(string str, int start){ int n=str.length()-1; if(start == n){ cout <<"\t\t" << str << endl; count++; }else{ for(int i=start;i<= n;i++){ swap(str[start],str[i]); permute(str,start + 1); } } } |
In the main function, we first take up the name of the user and then give this name to the permute method which performs all the permutations and displays them on the output screen and at the end, it prints the total number of ways.
Write a program to print all permutations of a given string in C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | #include <iostream> using namespace std; int count=0; void swap(char *a, char *b){ char temp = *a; *a = *b; *b = temp; } void permute(string str, int start){ int n=str.length()-1; if(start == n){ cout <<"\t\t" << str << endl; count++; }else{ for(int i=start;i<= n;i++){ swap(str[start],str[i]); permute(str,start + 1); } } } int main() { string name; cout << "Enter your name : "; cin >> name; cout << "Here is all the permutations of your name : " << endl<< endl; permute(name,0); cout << endl <<"Total permutations of your name is " <<count; return 0; } |
Output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | Enter your name : Mark Here is all the permutations of your name : Mark Makr Mrak Mrka Mkar Mkra aMrk aMkr arMk arkM akMr akrM rMak rMka raMk rakM rkMa rkaM kMar kMra kaMr karM krMa kraM Total permutations of your name is 24 |
This code is “logically” wrong, even though it will “technically” pass the test cases. What it is missing is, after the recursive call to the permute function (line#21), it should also restore the string order by calling this code again:
swap(str[start],str[i]);
In other words, this line should be called twice, before AND after the permute() function call. This is to restore the string order, hence the “backtrace”. Otherwise it will give you the wrong result. But you may ask, why does the current “wrong” code still works? That is because the string str is passed by value which means after the recursion call the string str is actually not changed which behaves as if it is “restored”. To prove this, simply make the string str as a reference type, such as string &str in the permute function parameter, then this code will fail. Because now it is passed by reference and thus the str itself is not restored after each call and therefore it would have wrong results. The “proper” way is to add that line to swap back the characters after the permute() call. And with this, even if you change the string type to a reference or pointer then it would still work as expected.