Print distinct sorted permutations with duplicates allowed in input | C ++ program to print all permutations of a string in sorted order . ; Calculating factorial of a number ; Method to find total number of permutations ; Building Map to store frequencies of all characters . ; Traversing map and finding duplicate elements . ; Start traversing from the end and find position ' i - 1' of the first character which is greater than its successor . ; Finding smallest character after ' i - 1' and greater than temp [ i - 1 ] ; Swapping the above found characters . ; Sort all digits from position next to ' i - 1' to end of the string . ; Print the String ; Sorting String ; Print first permutation ; Finding the total permutations ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int factorial ( int n ) { int f = 1 ; for ( int i = 1 ; i <= n ; i ++ ) f = f * i ; return f ; } int calculateTotal ( string temp , int n ) { int f = factorial ( n ) ; map < char , int > hm ; for ( int i = 0 ; i < temp . length ( ) ; i ++ ) { hm [ temp [ i ] ] ++ ; } for ( auto e : hm ) { int x = e . second ; if ( x > 1 ) { int temp5 = factorial ( x ) ; f /= temp5 ; } return f ; } } static void nextPermutation ( string & temp ) { int i ; for ( i = temp . length ( ) - 1 ; i > 0 ; i -- ) if ( temp [ i ] > temp [ i - 1 ] ) break ; int min = i ; int j , x = temp [ i - 1 ] ; for ( j = i + 1 ; j < temp . length ( ) ; j ++ ) if ( ( temp [ j ] < temp [ min ] ) and ( temp [ j ] > x ) ) min = j ; swap ( temp [ i - 1 ] , temp [ min ] ) ; sort ( temp . begin ( ) + i , temp . end ( ) ) ; cout << temp << endl ; } void printAllPermutations ( string s ) { string temp ( s ) ; sort ( temp . begin ( ) , temp . end ( ) ) ; cout << temp << endl ; int total = calculateTotal ( temp , temp . length ( ) ) ; for ( int i = 1 ; i < total ; i ++ ) { nextPermutation ( temp ) ; } } int main ( ) { string s = " AAB " ; printAllPermutations ( s ) ; }