Print Distinct Sorted Permutations with Duplicates in C++

In this programming problem, we are given a string and we have to print the distinct sorted permutations of the string elements that can be formed. The condition with this problem is that the string may contain a character that will arise more than one time. Also, the given string is inputted in sorted order.

Let’s take an example to understand the concept better,

Input : ABD
Output : ABD , ADB , BAD , BDA , DAB , DBA
INPUT : RSTU
OUTPUT : RSTU , RSUT , RTSU , RTUS , RUST , RUTS , SRTU , SRUT , STRU , STUR , SURT , SUTR , TRSU , TRUS , TSRU , TSUR , TURS , TUSR , URST , URTS , USRT , USTR , UTRS , UTSR.

PERMUTATION is rearranging all the elements of a set based on a specific sequence or type. The set may be ordered or may not be ordered.

Now as we have learned everything about the problem. Let’s try to create a logic to solve the problem,

We know some mathematical formula related to permutations. The total number of strings that are generated by a string that contains n characters and all of the are distinct is given by n!. If there are characters in the string that are repeating itself then, the number of strings is given by n! / i!.

For string STURS, the total number of string that can be generated is 5! / 2! = 60. Since s occurs 2 times in the string.

Using this we know the number of string created. Now, we have to create those strings. For this first we will sort the string if not (string inputted will be sorted) so that the final string will be in a sorted form. Now, fix the first character of the string and find the permutation of all the rest and so on. This will give all the required permutations in a sorted manner.

For example,

Input − RST

Logic −

From this string total 3! = 6 permutations can be formed.

Let’s fix R and find permutations from s and t. This will give 2 strings RST, RTS.

Similarly fixing S will give SRT, STR. And fixing T will give TRS, TSR.

So, this will give the output as - RST, RTS, SRT, STR, TRS, TSR. which are in sort order.

Now, let's create a program to solve this problem,

Example

#include <bits/stdc++.h>
using namespace std;
bool swaper(char str[], int start, int curr){
   for (int i = start; i < curr; i++)
      if (str[i] == str[curr])
      return 0;
   return 1;
}
void printPermutations(char str[], int index, int n){
   if (index >= n) {
      cout<<str<<"\t";
      return;
   }
   for (int i = index; i < n; i++) {
      bool check = swaper(str, index, i);
      if (check) {
         swap(str[index], str[i]);
         printPermutations(str, index + 1, n);
         swap(str[index], str[i]);
      }
   }
}
int main(){
   char str[] = "AABC";
   int n = strlen(str);
   cout<<"The string is : "<<str<<end;
   cout<<"The distinct sorted permutations are : \t";
   printPermutations(str, 0, n);
   return 0;
}

Output

The string is : AABC
The distinct sorted permutations are : AABC AACB
   ABAC ABCA ACBA ACAB BAAC
   BACA BCAA CABA CAAB CBAA