Minimum cost to generate any permutation of the given string | Function that returns true if the current bit is set ; 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 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
function check ( mask , i ) { var c = ( mask & ( 1 << i ) ) ; return c != 0 ; } function solve ( a , s , n , prev , mask , dp ) { if ( mask == 0 ) return 0 ; if ( dp [ mask ] [ prev + 1 ] != - 1 ) return dp [ mask ] [ prev + 1 ] ; var ans = 10000 ; for ( var i = 0 ; i < s . length ; i ++ ) { var id = s [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ; if ( check ( mask , id ) ) { if ( prev == - 1 ) { ans = Math . min ( ans , solve ( a , s , n , id , mask ^ ( 1 << id ) , dp ) ) ; } else { ans = Math . min ( ans , a [ prev ] [ id ] + solve ( a , s , n , id , mask ^ ( 1 << id ) , dp ) ) ; } } } dp [ mask ] [ prev + 1 ] = ans ; return ans ; } function generatePermutation ( mask , n , a , s ) { var dp = Array . from ( Array ( ( 1 << n ) + 5 ) , ( ) => Array ( n + 5 ) . fill ( - 1 ) ) ; for ( var i = 0 ; i < s . length ; i ++ ) { var id = s [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ; mask |= ( 1 << id ) ; } document . write ( solve ( a , s , n , - 1 , mask , dp ) + " " ) ; } var N = 5 ; var str = " " ; var 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 ] ] ; generatePermutation ( 0 , N , mat , str ) ;