C++ Program to Print All Permutations of a Given String
Posted by Superadmin on August 10 2022 13:07:30

C++ Program to Print All Permutations of a Given String

Method 1: Print all permutations of a given string

This C++ Program Permute All Letters of an Input String. It iterates from the 0th letter to the last letter in a string, swaps values and recursively call permute function to print values.

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.

Problem Description

The time complexity of this algorithm is O(n).

Problem Solution

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.

Program/Source Code

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;
}

Program Explanation

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.

Runtime Test Cases

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

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.

Problem Description

1. This algorithm prints the permutation of a string with all distinct characters.
2. The time complexity of this algorithm is O(n!).

Problem Solution

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.

Program/Source Code

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;
}

Program Explanation

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.

Runtime Test Cases

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