Minimum cost to generate any permutation of the given string | Function to find the minimum cost to form any permutation of string s ; Base Case ; Return the precomputed state ; Iterate over the string and check all possible characters available for current position ; Check if character can be placed at current position ; As there is no previous character so the cost for 1 st character is 0 ; Find the cost of current character and move to next position ; Store the answer for each current state ; Function that returns True if the current bit is set ; Function that generates any permutation of the given string with minimum cost ; Initialize dp table ; Set all the bits of the current character id ; Minimum cost of generating the permutation ; Driver Code ; Function Call
def solve ( a , s , n , prev , mask , dp ) : NEW_LINE INDENT if ( mask == 0 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( dp [ mask ] [ prev + 1 ] != - 1 ) : NEW_LINE INDENT return dp [ mask ] [ prev + 1 ] ; NEW_LINE DEDENT ans = 10000 ; NEW_LINE for i in range ( len ( s ) ) : NEW_LINE INDENT id = ord ( s [ i ] ) - ord ( ' a ' ) ; NEW_LINE if ( check ( mask , id ) ) : NEW_LINE INDENT if ( prev == - 1 ) : NEW_LINE INDENT ans = min ( ans , solve ( a , s , n , id , mask ^ ( 1 << id ) , dp ) ) ; NEW_LINE DEDENT else : NEW_LINE INDENT ans = min ( ans , a [ prev ] [ id ] + solve ( a , s , n , id , mask ^ ( 1 << id ) , dp ) ) ; NEW_LINE DEDENT DEDENT DEDENT dp [ mask ] [ prev + 1 ] = ans ; NEW_LINE return ans ; NEW_LINE DEDENT def check ( mask , i ) : NEW_LINE INDENT c = ( mask & ( 1 << i ) ) ; NEW_LINE return c != 0 ; NEW_LINE DEDENT def generatePermutation ( mask , n , a , s ) : NEW_LINE INDENT dp = [ [ - 1 for i in range ( n + 5 ) ] for j in range ( ( 1 << n ) + 5 ) ] NEW_LINE for i in range ( len ( s ) ) : NEW_LINE INDENT id = ord ( s [ i ] ) - ord ( ' a ' ) ; NEW_LINE mask |= ( 1 << id ) ; NEW_LINE DEDENT print ( solve ( a , s , n , - 1 , mask , dp ) ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 5 ; NEW_LINE str = " abcde " ; NEW_LINE mat = [ [ 0 , 5 , 1 , 5 , 3 ] , [ 4 , 0 , 9 , 4 , 2 ] , [ 7 , 9 , 0 , 10 , 7 ] , [ 1 , 2 , 8 , 0 , 2 ] , [ 3 , 9 , 7 , 7 , 0 ] ] ; NEW_LINE generatePermutation ( 0 , N , mat , str ) ; NEW_LINE DEDENT