Case 1: A program to find a permutation of a given string: Enter the string: aabcddd The number of possible permutation are: 420 Case 2: A program to find a permutation of a given string: Enter the string: vghhnhkkkvv The number of possible permutation are: 184800
Users Online
· Members Online: 0
· Total Members: 188
· Newest Member: meenachowdary055
Forum Threads
Latest Articles
Articles Hierarchy
C++ Program to Print All Permutations of a Given String
C++ Program to Print All Permutations of a Given String
Method 1: Print all permutations of a given string
The program has input as a string. This prints permutation of all letters of an input string.
Here is the source code of the C++ Program to Find Permute All Letters of an Input String. The C++ program is successfully compiled and run on g++-4.3.2 on a Linux system. The program output is also shown below.
-
//This is a C++ Program to Permute All Letters Of An Input String.
-
#include <iostream>
-
#include <string>
-
#include <algorithm>
-
-
using namespace std;
-
void permute (string temp_str, int start, int end)
-
{
-
int i;
-
if (start == end){
-
cout << temp_str << " ";
-
}
-
else{
-
for (int i = start; i < temp_str.length (); ++i){
-
swap (temp_str[start], temp_str[i]);
-
permute (temp_str, start + 1, end);
-
swap (temp_str[start], temp_str[i]);
-
}
-
}
-
}
-
int main()
-
{
-
string input_str;
-
bool flag = false;
-
cout << "Enter String : ";
-
cin >> input_str;
-
for (int i = 0; i < input_str.length () - 1; ++i)
-
{
-
if (input_str[i] == input_str[i + 1])
-
{
-
flag = true;
-
break;
-
}
-
else {
-
flag = false;
-
break;
-
}
-
}
-
if (flag)
-
{
-
cout << "The permutation of " << input_str << " is : " << input_str << endl;
-
}
-
else
-
{
-
cout << "The permutations of " << input_str << " are : " << endl;
-
permute (input_str, 0, input_str.length () - 1);
-
}
-
cout << endl;
-
return 0;
-
}
Output :
$ g++ PermuteString.cpp $ ./a.out Enter String : bac The permutations of bac are : bac bca abc acb cab cba Enter String : aaaa The permutation of aaaaa is : aaaaa Enter String : b The permutations of b are : b
Method 2: Find the number of possible permutations for a given string
This algorithm prints a total number of permutations possible for a given string.
The time complexity of this algorithm is O(n).
1. This algorithm takes the input of the string.
2. Then it checks for the repetition of the characters.
3. Compute the permutation and print the result.
4. Exit.
Here is the source code of the C++ Program to find the number of permutations of a given string.
#include<iostream> #include<string.h> using namespace std; // A function to find the factorial. int factorial(int n) { int i; for(i = n-1; i > 1; i--) n *= i; return n; } // A function to calculate the total number of permutation possible for the given set. int CountPermutation(char *str) { int countoccur[26] = {0}, len, i, res; len = strlen(str); // Count the occurrence of each character. for(i = 0; i < len; i++) { countoccur[str[i]-'a']++; } res = factorial(len); // Divide the length factorial by the factorial of number of occurrence of each character. for(i = 0; i < 26; i++) { if(countoccur[i] > 1) res = res/factorial(countoccur[i]); } return res; } int main() { int result; char str[100]; cout<<"A program to find a permutation of a given string: "; cout<<"\n\n\tEnter the string: "; cin>>str; // Get result using CountPermutation(). result = CountPermutaion(str); cout<<"\nThe number of possible permutation are: "<<result; return 0; }
1. Take the input of the string.
2. Call CountPermutation() with the string as an argument.
3. Inside CountPermutation, Firstly Count the number of occurrence of each character of the string.
4. Calculate the factorial of the length of the string and store in ‘res’.
5. Divide the ‘res’ by the factorial of a number of occurrence of each character if they count more than 1.
6. Return to main and print the result.
7. Exit.
Method 3: Generating all possible permutations of a given string
This is a C++ program that permutes every character in an input string along with the number of possible permutations.
1. This algorithm prints the permutation of a string with all distinct characters.
2. The time complexity of this algorithm is O(n!).
1. This algorithm takes the input of a string with all distinct characters N value.
2. It places each character to every index by swapping values.
3. After each completion calls again the between those indexes to regain the earlier stage.
4. Exit.
Here is the source code of the C++ Program to permute all letters of an input string.
#include<iostream> #include<string.h> using namespace std; // A function to swap character values of the string using references. void swap (char *x, char *y) { char temp; temp = *x; *x = *y; *y = temp; } // A function to print permutation using recursion technique. void Permute(char *a, int i, int n) { int j; if (i == n-1) cout<<"\n"<<a; else { for (j = i; j < n; j++) { // Swap the character at ith index with every other value to get all the possible permutations. swap(a[i], a[j]); Permute(a, i + 1, n); swap(a[i], a[j]); } } } int main() { char str[21]; int len, count = 1; cout<<"\nEnter a string: "; cin>>str; len = strlen(str); for (i = 0; i < N; i++) { count *= (i+1); } // Print the permutation's count. cout<<"\nThe number of permutations possible is: "<<count; // Call permute() function to print all the permutation. Permute(str, 0, len); return 0; }
1. Take the string input from the user.
2. Compute the factorial of the length of the string, which will be the total number of permutation possible.
3. Call Permute(), with the string ‘str’, ‘i’ be the swap index and ‘len’ be the string length.
4. In Permute(), if the swap index is equal to ‘len-1’ then print the string as a new permutation.
5. Otherwise, swap every other character(use loop over j from i to n-1) after ‘i’ index with the character at ith value.
6. Recursively call Permute() with incremented value of the swap index ‘i’.
7. Again swap character at the ith index to the character at the jth index to get the earlier state of the string.
8. Exit.
Case 1: Enter a string: abc The number of permutations possible is: 6 abc acb bac bca cba cab Case 2: Enter a string: abcd The number of permutations possible is: 24 abcd abdc acbd acdb adcb adbc bacd badc bcad bcda bdca bdac cbad cbda cabd cadb cdab cdba dbca dbac dcba dcab dacb dabc