Print All Permutations with Repetition of Characters in C++

In this problem, we are given a string of n characters and we have to print all permutations of characters of the string. Repeating of characters of the string is allowed. The printing of permutation should be done in alphabetical order (lexicographically sorted order).

Let’s take an example to understand the topic better :

Input − XY

Output − XX, XY, YX, YY

To solve this problem, we need to use fix and recur logic. Here, we will fix one element at first index of the array and then recursively call for the next elements in the sequence.

Let’s see an implementation example which will make the solution clear to you.

Input string XY.

Fix first elements at 1 index: X_

Recursively call other elements and fill: XX -> XY

Now fix the next element at index1: Y_

Recursively call other elements and fill: YX-> YY

The same logic can be used for 3,4,n length string.

Example

#include <iostream>
#include<string.h>
using namespace std;
void printPermutations(char *str, char* permutations, int last, int index){
   int i, len = strlen(str);
   for ( i = 0; i < len; i++ ) {
      permutations[index] = str[i] ;
      if (index == last)
         cout<<permutations <<"\t";
      else
         printPermutations (str, permutations, last, index+1);
   }
}
int main() {
   char str[] = "ABC";
   cout<<"All permutations of the string with repetition of "<<str<<" are: "<<endl ;
   int len = strlen(str) ;
   char permutations[len];
   printPermutations (str, permutations, len-1, 0);
   return 0;
}

Output

All permutations of the string with repetition of ABC are:
AAA AAB AAC ABA ABB ABC ACA ACB ACC BAA BAB BAC BBA BBB BBC BCA BCB BCC CAA CAB CAC CBA CBB CBC CCA CCB CCC