Dada la string str de tamaño N que consiste en los primeros N alfabetos y una array mat[] de tamaño N*N donde mat[i][j] representa el costo de colocar el i -ésimo carácter del alfabeto antes del j -ésimo carácter en la string . La tarea es encontrar el costo mínimo para generar cualquier permutación de la string dada .
Ejemplos:
Entrada: 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}}
Salida: 8
Explicación:
La permutación ‘dbeac’ se puede generar a un costo mínimo de 8.
Costo de colocar d = 0 (ya que no hay carácter anterior)
Costo de colocar b después de d = mat[4][2] = 2
Costo de colocar e después de b = mat[2][5] = 2
Costo de colocar a después de e = mat[5 ][1] = 3
Costo de colocar c después de a = mat[1][3] = 1
Costo total = 2 + 2 + 3 + 1 = 8Entrada: 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 }}
Salida: 13
Enfoque ingenuo: la idea ingenua es generar todas las permutaciones posibles de la string dada y encontrar el costo de cada permutación. Luego imprima el costo mínimo entre todos los costos posibles.
Complejidad de tiempo: O(N*N!)
Espacio auxiliar: O(N!)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la programación dinámica con enmascaramiento de bits . Observe que todos los caracteres son distintos y solo hay 26 alfabetos posibles. Así que usa una máscara para almacenar la presencia de cada personaje. A continuación se muestran los pasos:
- Repita todos los caracteres de la string y coloque cada carácter en cada posición si está disponible, es decir, el bit está establecido en la máscara.
- Luego, coloque el personaje en la posición actual y calcule el costo de colocar al personaje.
- Muévase a la siguiente posición cambiando el bit del carácter actual.
- En cada iteración, la máscara representa el número de caracteres disponibles para la posición actual.
- Después de completar los pasos anteriores, imprima el costo mínimo entre todos los costos calculados.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns true
// if the current bit is set
bool check(int mask, int i)
{
int c = (mask & (1 << i));
return c != 0;
}
// Function to find the minimum cost
// to form any permutation of string s
int solve(vector<vector<int>> a, string s,
int n, int prev, int mask,
vector<vector<int>> dp)
{
// Base Case
if (mask == 0)
return 0;
// Return the precomputed state
if (dp[mask][prev + 1] != -1)
return dp[mask][prev + 1];
int ans = 10000;
// Iterate over the string and
// check all possible characters
// available for current position
for(int i = 0; i < s.length(); i++)
{
int id = s[i] - 'a';
// Check if character can be
// placed at current position
if (check(mask, id))
{
// As there is no previous
// character so the cost
// for 1st character is 0
if (prev == -1)
{
ans = min(ans, solve(a, s, n, id,
mask ^ (1 << id), dp));
}
// Find the cost of current
// character and move to next
// position
else
{
ans = min(ans, a[prev][id] +
solve(a, s, n, id,
mask ^ (1 << id), dp));
}
}
}
// Store the answer for each
// current state
dp[mask][prev + 1] = ans;
return ans;
}
// Function that generates any
// permutation of the given
// string with minimum cost
void generatePermutation(int mask, int n,
vector<vector<int>> a,
string s)
{
// Initialize dp table
vector<vector<int>> dp((1 << n) + 5 ,
vector<int> (n + 5, -1));
// Set all the bits of the
// current character id
for(int i = 0; i < s.length(); i++)
{
int id = s[i] - 'a';
mask |= (1 << id);
}
// Minimum cost of generating
// the permutation
cout << solve(a, s, n, -1, mask, dp)
<< endl;
}
// Driver Code
int main()
{
int N = 5;
string str = "abcde";
vector<vector<int>> 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 } };
// Function Call
generatePermutation(0, N, mat, str);
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// Java program for the above approach
import java.util.*;
public class Main {
// Function to find the minimum cost
// to form any permutation of string s
public static int solve(
int a[][], String s, int n,
int prev, int mask, int[][] dp)
{
// Base Case
if (mask == 0)
return 0;
// Return the precomputed state
if (dp[mask][prev + 1] != -1)
return dp[mask][prev + 1];
int ans = 10000;
// Iterate over the string and
// check all possible characters
// available for current position
for (int i = 0; i < s.length(); i++) {
int id = s.charAt(i) - 'a';
// Check if character can be
// placed at current position
if (check(mask, id)) {
// As there is no previous
// character so the cost
// for 1st character is 0
if (prev == -1) {
ans
= Math.min(ans,
solve(
a, s,
n, id,
mask ^ (1 << id),
dp));
}
// Find the cost of current
// character and move to next
// position
else {
ans = Math.min(
ans,
a[prev][id]
+ solve(
a, s,
n, id,
mask ^ (1 << id),
dp));
}
}
}
// Store the answer for each
// current state
dp[mask][prev + 1] = ans;
return ans;
}
// Function that returns true
// if the current bit is set
public static boolean
check(int mask, int i)
{
int c = (mask & (1 << i));
return c != 0;
}
// Function that generates any
// permutation of the given
// string with minimum cost
static void generatePermutation(
int mask, int n, int a[][],
String s)
{
// Initialize dp table
int dp[][] = new int[(1 << n) + 5][n + 5];
for (int i[] : dp)
Arrays.fill(i, -1);
// Set all the bits of the
// current character id
for (int i = 0;
i < s.length(); i++) {
int id = s.charAt(i) - 'a';
mask |= (1 << id);
}
// Minimum cost of generating
// the permutation
System.out.println(solve(
a, s, n, -1, mask, dp));
}
// Driver Code
public static void main(String args[])
{
int N = 5;
String str = "abcde";
int 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 } };
// Function Call
generatePermutation(0, N, mat, str);
}
}
Python3
# Python3 program for the
# above approach
# Function to find the
# minimum cost to form
# any permutation of
# string s
def solve(a, s, n, prev,
mask, dp):
# Base Case
if (mask == 0):
return 0;
# Return the precomputed state
if (dp[mask][prev + 1] != -1):
return dp[mask][prev + 1];
ans = 10000;
# Iterate over the string and
# check all possible characters
# available for current position
for i in range(len(s)):
id = ord(s[i]) - ord('a');
# Check if character can be
# placed at current position
if (check(mask, id)):
# As there is no previous
# character so the cost
# for 1st character is 0
if (prev == -1):
ans = min(ans,
solve(a, s,
n, id,
mask ^ (1 <<
id), dp));
# Find the cost of current
# character and move to next
# position
else:
ans = min(ans, a[prev][id] +
solve(a, s, n,
id, mask ^
(1 << id), dp));
# Store the answer for each
# current state
dp[mask][prev + 1] = ans;
return ans;
# Function that returns
# True if the current
# bit is set
def check(mask, i):
c = (mask & (1 << i));
return c != 0;
# Function that generates any
# permutation of the given
# string with minimum cost
def generatePermutation(mask, n,
a, s):
# Initialize dp table
dp = [[-1 for i in range(n + 5)]
for j in range((1 << n) + 5)]
# Set all the bits of the
# current character id
for i in range(len(s)):
id = ord(s[i]) - ord('a');
mask |= (1 << id);
# Minimum cost of generating
# the permutation
print(solve(a, s, n,
-1, mask, dp));
# Driver Code
if __name__ == '__main__':
N = 5;
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]];
# Function Call
generatePermutation(0, N,
mat, str);
# This code is contributed by gauravrajput1
C#
// C# program for the
// above approach
using System;
class GFG{
// Function to find the minimum cost
// to form any permutation of string s
public static int solve(int[,]a, String s, int n,
int prev, int mask, int[,] dp)
{
// Base Case
if (mask == 0)
return 0;
// Return the precomputed state
if (dp[mask,prev + 1] != -1)
return dp[mask, prev + 1];
int ans = 10000;
// Iterate over the string and
// check all possible characters
// available for current position
for (int i = 0;
i < s.Length; i++)
{
int id = s[i] - 'a';
// Check if character can be
// placed at current position
if (check(mask, id))
{
// As there is no previous
// character so the cost
// for 1st character is 0
if (prev == -1)
{
ans = Math.Min(ans,
solve(a, s, n, id,
mask ^ (1 << id), dp));
}
// Find the cost of current
// character and move to next
// position
else
{
ans = Math.Min(ans, a[prev,id] +
solve(a, s, n, id,
mask ^ (1 << id), dp));
}
}
}
// Store the answer for each
// current state
dp[mask, prev + 1] = ans;
return ans;
}
// Function that returns true
// if the current bit is set
public static bool check(int mask, int i)
{
int c = (mask & (1 << i));
return c != 0;
}
// Function that generates any
// permutation of the given
// string with minimum cost
static void generatePermutation(int mask, int n,
int[,]a, String s)
{
// Initialize dp table
int [,]dp = new int[(1 << n) + 5,
n + 5];
for(int i = 0;
i < (1 << n) + 5; i++)
for(int j = 0;
j < n + 5; j++)
dp[i, j] = -1;
// Set all the bits of the
// current character id
for (int i = 0;
i < s.Length; i++)
{
int id = s[i] - 'a';
mask |= (1 << id);
}
// Minimum cost of generating
// the permutation
Console.WriteLine(solve(a, s, n,
-1, mask, dp));
}
// Driver Code
public static void Main(String []args)
{
int N = 5;
String str = "abcde";
int [,]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}};
// Function Call
generatePermutation(0, N, mat, str);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for the above approach
// Function that returns true
// if the current bit is set
function check(mask, i)
{
var c = (mask & (1 << i));
return c != 0;
}
// Function to find the minimum cost
// to form any permutation of string s
function solve(a, s, n, prev, mask, dp)
{
// Base Case
if (mask == 0)
return 0;
// Return the precomputed state
if (dp[mask][prev + 1] != -1)
return dp[mask][prev + 1];
var ans = 10000;
// Iterate over the string and
// check all possible characters
// available for current position
for(var i = 0; i < s.length; i++)
{
var id = s[i].charCodeAt(0) - 'a'.charCodeAt(0);
// Check if character can be
// placed at current position
if (check(mask, id))
{
// As there is no previous
// character so the cost
// for 1st character is 0
if (prev == -1)
{
ans = Math.min(ans, solve(a, s, n, id,
mask ^ (1 << id), dp));
}
// Find the cost of current
// character and move to next
// position
else
{
ans = Math.min(ans, a[prev][id] +
solve(a, s, n, id,
mask ^ (1 << id), dp));
}
}
}
// Store the answer for each
// current state
dp[mask][prev + 1] = ans;
return ans;
}
// Function that generates any
// permutation of the given
// string with minimum cost
function generatePermutation(mask, n, a, s)
{
// Initialize dp table
var dp = Array.from(Array((1 << n) + 5), ()=> Array(n + 5).fill(-1));
// Set all the bits of the
// current character id
for(var i = 0; i < s.length; i++)
{
var id = s[i].charCodeAt(0) - 'a'.charCodeAt(0);
mask |= (1 << id);
}
// Minimum cost of generating
// the permutation
document.write( solve(a, s, n, -1, mask, dp) + "<br>");
}
// Driver Code
var N = 5;
var str = "abcde";
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 ] ];
// Function Call
generatePermutation(0, N, mat, str);
// This code is contributed by noob2000.
</script>
Producción:
8
Complejidad de tiempo: O(N*2 N )
Espacio auxiliar: O(N*2 N )
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA