Minimum cost to generate any permutation of the given string

Given string str of size N consisting of the first N alphabets and a matrix mat[] of size N*N where mat[i][j] represents the cost of placing i^th character of the alphabet before the j^th character in the string. The task is to find the minimum cost to generate any permutation of the given string.

Examples: 

Input:str = “abcde”, 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}} 
Output: 8 
Explanation: 
Permutation ‘dbeac’ can be generated at a minimum cost of 8. 
Cost of placing d = 0 (since there is no prev character) 
Cost of placing b after d = mat[4][2] = 2 
Cost of placing e after b = mat[2][5] = 2 
Cost of placing a after e = mat[5][1] = 3 
Cost of placing c after a = mat[1][3] = 1 
Total cost = 2 + 2 + 3 + 1 = 8 

Input: str = “abcde”, mat[][] = {{0, 9, 4, 8, 10}, {7, 0, 9, 5, 5}, {2, 8, 0, 4, 1}, {4, 10, 5, 0, 5}, {4, 3, 4, 7, 0 }} 
Output: 13 

Naive Approach: The naive idea is to generate all possible permutations of the given string and find the cost of every permutation. Then print the minimum cost among all possible costs.

Time Complexity: O(N*N!) 
Auxiliary Space: O(N!)

Efficient Approach: To optimize the above approach the idea is to use Dynamic Programming with Bit Masking. Observe that all the characters are distinct and there are only 26 alphabets possible. So use a mask to store the presence of each character. Below are the steps: 

1. Iterate through all characters of the string and place each character at each position if it is available i.e., the bit is set in the mask.
2. Then, place the character in the current position and calculate the cost of placing the character.
3. Move to the next position by flipping the bit of the current character.
4. At each iteration, the mask represents the number of available characters for the current position.
5. After completing the above steps, print the minimum cost among all the costs calculated.

Below is the implementation of the above approach:

8

Time Complexity: O(N*2^N) 
Auxiliary Space: O(N*2^N)

Using Brute Force with Recursion in python:

Approach:

The idea is to generate all possible permutations of the given string and calculate the cost for each permutation. Finally, return the minimum cost among all the permutations.

The get_min_cost function takes two inputs, a string str and a 2D matrix mat that represents the cost of swapping each pair of characters. The function returns the minimum cost of swapping any pair of characters in the input string such that the resulting string is lexicographically sorted.

The function first generates all permutations of the input string using a recursive function permute, which takes the current permutation string s, left and right indices of the current permutation l and r respectively. The function generates permutations by swapping each character with every other character in the string, recursively calling itself for each swap until the left and right indices are the same, indicating that the string is fully permuted.

For each permutation, the function calculates the cost of swapping pairs of characters using the input matrix mat and returns the minimum cost of all permutations. The cost is calculated by iterating through each character in the permutation, and adding the cost of swapping it with the previous character. The cost of swapping two characters is obtained by indexing the matrix using the ASCII value of the characters.

8

Time Complexity: O(n!), where n is the length of the string. (as we generate all permutations)
Space Complexity: O(n), where n is the length of the string. (as we store the current permutation in memory)

Approch 3 : Dynamic Programming 

The provided code solves the given problem using dynamic programming. Memorization is employed to prevent recomputations and store the status of the subproblems. The current state is sent to the main function “solve” as (mask, prev), where “mask” denotes the set of characters that are now accessible and “prev” denotes the character that was previously positioned. The string is then iterated over, and each conceivable character that could fit in the present location is checked. It repeatedly calls’solve’ with the updated state and computes the cost of inserting the current character based on the previous character and the cost matrix ‘a’ for each character that may be placed at the current position. The current state’s dp table then contains the character placement with the lowest cost out of all potential character placements.

Algorithm Steps of the given code are as follows:

1. Define a function check() to check if the current bit is set in the mask.
2. Define a recursive function solve() to find the minimum cost to generate any permutation of the given string.
3. In solve(), check for the base case where mask becomes 0, i.e., all the characters have been used.
4. In solve(), check if the current state has already been computed in the dp table, if yes, then return the precomputed value.
5. In solve(), iterate over the string and check all possible characters available for the current position.
6. In solve(), if the character can be placed at the current position, then check if there is no previous character, in which case the cost for the first character is 0.
7. In solve(), else find the cost of the current character and move to the next position.
8. In solve(), store the answer for each current state in the dp table.
9. Define a function generatePermutation() to generate any permutation of the given string with minimum cost.
10. In generatePermutation(), initialize the dp table and set all the bits of the current character id.
11. In generatePermutation(), call the solve() function with initial parameters and output the minimum cost.
12. In main(), define the input string and cost matrix and call the generatePermutation() function with the inputs.
13. End of the program.

8

Time Complexity :  O(N * 2^N), where N is the size of the string.

Space Auxilitary Complexity : O(2^N * N).