Number of palindromic permutations | Set 1 | Python3 program to find number of palindromic permutations of a given string ; Returns factorial of n ; Returns count of palindromic permutations of str . ; Count frequencies of all characters ; Since half of the characters decide count of palindromic permutations , we take ( n / 2 ) ! ; To make sure that there is at most one odd occurring char ; Traverse through all counts ; To make sure that the string can permute to form a palindrome ; If there are more than one odd occurring chars ; Divide all permutations with repeated characters ; Driver code
MAX = 256 NEW_LINE def fact ( n ) : NEW_LINE INDENT res = 1 NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT res = res * i NEW_LINE DEDENT return res NEW_LINE DEDENT def countPalinPermutations ( str ) : NEW_LINE INDENT global MAX NEW_LINE n = len ( str ) NEW_LINE freq = [ 0 ] * MAX ; NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT freq [ ord ( str [ i ] ) ] = freq [ ord ( str [ i ] ) ] + 1 ; NEW_LINE DEDENT res = fact ( int ( n / 2 ) ) NEW_LINE oddFreq = False NEW_LINE for i in range ( 0 , MAX ) : NEW_LINE INDENT half = int ( freq [ i ] / 2 ) NEW_LINE if ( freq [ i ] % 2 != 0 ) : NEW_LINE INDENT if ( oddFreq == True ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT oddFreq = True NEW_LINE DEDENT res = int ( res / fact ( half ) ) NEW_LINE DEDENT return res NEW_LINE DEDENT str = " gffg " NEW_LINE print ( countPalinPermutations ( str ) ) NEW_LINE