Print distinct sorted permutations with duplicates allowed in input | Python3 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
from collections import defaultdict NEW_LINE def factorial ( n ) : NEW_LINE INDENT f = 1 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT f = f * i NEW_LINE DEDENT return f NEW_LINE DEDENT def calculateTotal ( temp , n ) : NEW_LINE INDENT f = factorial ( n ) NEW_LINE hm = defaultdict ( int ) NEW_LINE for i in range ( len ( temp ) ) : NEW_LINE INDENT hm [ temp [ i ] ] += 1 NEW_LINE DEDENT for e in hm : NEW_LINE INDENT x = hm [ e ] NEW_LINE if ( x > 1 ) : NEW_LINE INDENT temp5 = factorial ( x ) NEW_LINE f //= temp5 NEW_LINE DEDENT return f NEW_LINE DEDENT DEDENT def nextPermutation ( temp ) : NEW_LINE INDENT for i in range ( len ( temp ) - 1 , 0 , - 1 ) : NEW_LINE INDENT if ( temp [ i ] > temp [ i - 1 ] ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT min = i NEW_LINE x = temp [ i - 1 ] NEW_LINE for j in range ( i + 1 , len ( temp ) ) : NEW_LINE INDENT if ( ( temp [ j ] < temp [ min ] ) and ( temp [ j ] > x ) ) : NEW_LINE INDENT min = j NEW_LINE DEDENT DEDENT temp [ i - 1 ] , temp [ min ] = ( temp [ min ] , temp [ i - 1 ] ) NEW_LINE temp [ i : ] . sort ( ) NEW_LINE print ( ' ' . join ( temp ) ) NEW_LINE DEDENT def printAllPermutations ( s ) : NEW_LINE INDENT temp = list ( s ) NEW_LINE temp . sort ( ) NEW_LINE print ( ' ' . join ( temp ) ) NEW_LINE total = calculateTotal ( temp , len ( temp ) ) NEW_LINE for i in range ( 1 , total ) : NEW_LINE INDENT nextPermutation ( temp ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " AAB " NEW_LINE printAllPermutations ( s ) NEW_LINE DEDENT