Print distinct sorted permutations with duplicates allowed in input | Java program to print all permutations of a string in sorted order . ; Calculating factorial of a number ; Method to print the array ; Method to find total number of permutations ; Building HashMap to store frequencies of all characters . ; Traversing hashmap 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
import java . io . * ; import java . util . * ; class Solution { static int factorial ( int n ) { int f = 1 ; for ( int i = 1 ; i <= n ; i ++ ) f = f * i ; return f ; } static void print ( char [ ] temp ) { for ( int i = 0 ; i < temp . length ; i ++ ) System . out . print ( temp [ i ] ) ; System . out . println ( ) ; } static int calculateTotal ( char [ ] temp , int n ) { int f = factorial ( n ) ; HashMap < Character , Integer > hm = new HashMap < Character , Integer > ( ) ; for ( int i = 0 ; i < temp . length ; i ++ ) { if ( hm . containsKey ( temp [ i ] ) ) hm . put ( temp [ i ] , hm . get ( temp [ i ] ) + 1 ) ; else hm . put ( temp [ i ] , 1 ) ; } for ( Map . Entry e : hm . entrySet ( ) ) { Integer x = ( Integer ) e . getValue ( ) ; if ( x > 1 ) { int temp5 = factorial ( x ) ; f = f / temp5 ; } } return f ; } static void nextPermutation ( char [ ] 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 ] ) && ( temp [ j ] > x ) ) min = j ; char temp_to_swap ; temp_to_swap = temp [ i - 1 ] ; temp [ i - 1 ] = temp [ min ] ; temp [ min ] = temp_to_swap ; Arrays . sort ( temp , i , temp . length ) ; print ( temp ) ; } static void printAllPermutations ( String s ) { char temp [ ] = s . toCharArray ( ) ; Arrays . sort ( temp ) ; print ( temp ) ; int total = calculateTotal ( temp , temp . length ) ; for ( int i = 1 ; i < total ; i ++ ) nextPermutation ( temp ) ; } public static void main ( String [ ] args ) { String s = " AAB " ; printAllPermutations ( s ) ; } }