Impresión de corchetes en el problema de multiplicación de strings de arrays

Prerrequisito: Programación Dinámica | Conjunto 8 (Multiplicación de strings de arrays)

Dada una secuencia de arrays, encuentre la forma más eficiente de multiplicar estas arrays. El problema no es realmente realizar las multiplicaciones, sino simplemente decidir en qué orden realizar las multiplicaciones.

Tenemos muchas opciones para multiplicar una string de arrays porque la multiplicación de arrays es asociativa. En otras palabras, no importa cómo pongamos entre paréntesis el producto, el resultado será el mismo. Por ejemplo, si tuviéramos cuatro arrays A, B, C y D, tendríamos: 

(ABC)D = (AB)(CD) = A(BCD) = ....

Sin embargo, el orden en que ponemos el producto entre paréntesis afecta la cantidad de operaciones aritméticas simples necesarias para calcular el producto o la eficiencia. Por ejemplo, suponga que A es una array de 10 × 30, B es una array de 30 × 5 y C es una array de 5 × 60. Después,  

(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations
A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.

Claramente, el primer paréntesis requiere menos número de operaciones.

Dada una array p[] que representa la string de arrays tal que la i-ésima array Ai es de dimensión p[i-1] xp[i]. Necesitamos escribir una función MatrixChainOrder() que devuelva el número mínimo de multiplicaciones necesarias para multiplicar la string. 

Input:  p[] = {40, 20, 30, 10, 30}  
Output: Optimal parenthesization is  ((A(BC))D)
        Optimal cost of parenthesization is 26000
There are 4 matrices of dimensions 40x20, 20x30, 
30x10 and 10x30. Let the input 4 matrices be A, B, 
C and D.  The minimum number of  multiplications are 
obtained by putting parenthesis in following way
(A(BC))D --> 20*30*10 + 40*20*10 + 40*10*30

Input: p[] = {10, 20, 30, 40, 30} 
Output: Optimal parenthesization is (((AB)C)D)
        Optimal cost of parenthesization is 30000
There are 4 matrices of dimensions 10x20, 20x30, 
30x40 and 40x30. Let the input 4 matrices be A, B, 
C and D.  The minimum number of multiplications are 
obtained by putting parenthesis in following way
((AB)C)D --> 10*20*30 + 10*30*40 + 10*40*30

Input: p[] = {10, 20, 30}  
Output: Optimal parenthesization is (AB)
        Optimal cost of parenthesization is 6000
There are only two matrices of dimensions 10x20 
and 20x30. So there is only one way to multiply 
the matrices, cost of which is 10*20*30

Este problema es principalmente una extensión de la publicación anterior . En la publicación anterior, hemos discutido el algoritmo para encontrar solo el costo óptimo. Aquí también necesitamos paréntesis de impresión.

La idea es almacenar el punto de ruptura óptimo para cada subexpresión (i, j) en un corchete de array 2D [n] [n]. Una vez que hemos construido la array de corchetes, podemos imprimir paréntesis usando el siguiente código. 

// Prints parenthesization in subexpression (i, j)
printParenthesis(i, j, bracket[n][n], name)
{
    // If only one matrix left in current segment
    if (i == j)
    {
        print name;
        name++;
        return;
    }

    print "(";

    // Recursively put brackets around subexpression
    // from i to bracket[i][j].
    printParenthesis(i, bracket[i][j], bracket, name);

    // Recursively put brackets around subexpression
    // from bracket[i][j] + 1 to j.
    printParenthesis(bracket[i][j]+1, j, bracket, name);

    print ")";
}

A continuación se muestra la implementación de los pasos anteriores.

C++

// C++ program to print optimal parenthesization
// in matrix chain multiplication.
#include <bits/stdc++.h>
using namespace std;
 
// Function for printing the optimal
// parenthesization of a matrix chain product
void printParenthesis(int i, int j, int n, int* bracket,
                      char& name)
{
    // If only one matrix left in current segment
    if (i == j) {
        cout << name++;
        return;
    }
 
    cout << "(";
 
    // Recursively put brackets around subexpression
    // from i to bracket[i][j].
    // Note that "*((bracket+i*n)+j)" is similar to
    // bracket[i][j]
    printParenthesis(i, *((bracket + i * n) + j), n,
                     bracket, name);
 
    // Recursively put brackets around subexpression
    // from bracket[i][j] + 1 to j.
    printParenthesis(*((bracket + i * n) + j) + 1, j, n,
                     bracket, name);
    cout << ")";
}
 
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
// Please refer below article for details of this
// function
// https://goo.gl/k6EYKj
void matrixChainOrder(int p[], int n)
{
    /* For simplicity of the program, one extra
       row and one extra column are allocated in
        m[][]. 0th row and 0th column of m[][]
        are not used */
    int m[n][n];
 
    // bracket[i][j] stores optimal break point in
    // subexpression from i to j.
    int bracket[n][n];
 
    /* m[i,j] = Minimum number of scalar multiplications
    needed to compute the matrix A[i]A[i+1]...A[j] =
    A[i..j] where dimension of A[i] is p[i-1] x p[i] */
 
    // cost is zero when multiplying one matrix.
    for (int i = 1; i < n; i++)
        m[i][i] = 0;
 
    // L is chain length.
    for (int L = 2; L < n; L++)
    {
        for (int i = 1; i < n - L + 1; i++)
        {
            int j = i + L - 1;
            m[i][j] = INT_MAX;
            for (int k = i; k <= j - 1; k++)
            {
                // q = cost/scalar multiplications
                int q = m[i][k] + m[k + 1][j]
                        + p[i - 1] * p[k] * p[j];
                if (q < m[i][j])
                {
                    m[i][j] = q;
 
                    // Each entry bracket[i,j]=k shows
                    // where to split the product arr
                    // i,i+1....j for the minimum cost.
                    bracket[i][j] = k;
                }
            }
        }
    }
 
    // The first matrix is printed as 'A', next as 'B',
    // and so on
    char name = 'A';
 
    cout << "Optimal Parenthesization is : ";
    printParenthesis(1, n - 1, n, (int*)bracket, name);
    cout << "nOptimal Cost is : " << m[1][n - 1];
}
 
// Driver code
int main()
{
    int arr[] = { 40, 20, 30, 10, 30 };
    int n = sizeof(arr) / sizeof(arr[0]);
    matrixChainOrder(arr, n);
    return 0;
}

Java

// Java program to print optimal parenthesization
// in matrix chain multiplication.
class GFG
{
  static char name;
 
  // Function for printing the optimal
  // parenthesization of a matrix chain product
  static void printParenthesis(int i, int j,
                               int n, int[][] bracket)
  {
 
    // If only one matrix left in current segment
    if (i == j)
    {
      System.out.print(name++);
      return;
    }
    System.out.print("(");
 
    // Recursively put brackets around subexpression
    // from i to bracket[i][j].
    // Note that "*((bracket+i*n)+j)" is similar to
    // bracket[i][j]
    printParenthesis(i, bracket[i][j], n, bracket);
 
    // Recursively put brackets around subexpression
    // from bracket[i][j] + 1 to j.
    printParenthesis(bracket[i][j] + 1, j, n, bracket);
    System.out.print(")");
  }
 
  // Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
  // Please refer below article for details of this
  // function
  // https://goo.gl/k6EYKj
  static void matrixChainOrder(int p[], int n)
  {
    /*
         * For simplicity of the program,
         one extra row and one extra column are
         * allocated in m[][]. 0th row and
         0th column of m[][] are not used
         */
    int[][] m = new int[n][n];
 
    // bracket[i][j] stores optimal break point in
    // subexpression from i to j.
    int[][] bracket = new int[n][n];
 
    /*
         * m[i,j] = Minimum number of scalar
         multiplications needed to compute the
         * matrix A[i]A[i+1]...A[j] = A[i..j] where
         dimension of A[i] is p[i-1] x p[i]
         */
 
    // cost is zero when multiplying one matrix.
    for (int i = 1; i < n; i++)
      m[i][i] = 0;
 
    // L is chain length.
    for (int L = 2; L < n; L++)
    {
      for (int i = 1; i < n - L + 1; i++)
      {
        int j = i + L - 1;
        m[i][j] = Integer.MAX_VALUE;
        for (int k = i; k <= j - 1; k++)
        {
 
          // q = cost/scalar multiplications
          int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
          if (q < m[i][j])
          {
            m[i][j] = q;
 
            // Each entry bracket[i,j]=k shows
            // where to split the product arr
            // i,i+1....j for the minimum cost.
            bracket[i][j] = k;
          }
        }
      }
    }
 
    // The first matrix is printed as 'A', next as 'B',
    // and so on
    name = 'A';
    System.out.print("Optimal Parenthesization is : ");
    printParenthesis(1, n - 1, n, bracket);
    System.out.print("\nOptimal Cost is : " + m[1][n - 1]);
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int arr[] = { 40, 20, 30, 10, 30 };
    int n = arr.length;
    matrixChainOrder(arr, n);
  }
}
 
// This code is contributed by sanjeev2552

C#

// C# program to print optimal parenthesization
// in matrix chain multiplication.
using System;
 
class GFG{
     
static char name;
 
// Function for printing the optimal
// parenthesization of a matrix chain product
static void printParenthesis(int i, int j,
                             int n, int[,] bracket)
{
     
    // If only one matrix left in current segment
    if (i == j)
    {
        Console.Write(name++);
        return;
    }
    Console.Write("(");
     
    // Recursively put brackets around subexpression
    // from i to bracket[i,j].
    // Note that "*((bracket+i*n)+j)" is similar to
    // bracket[i,j]
    printParenthesis(i, bracket[i, j], n, bracket);
     
    // Recursively put brackets around subexpression
    // from bracket[i,j] + 1 to j.
    printParenthesis(bracket[i, j] + 1, j, n, bracket);
    Console.Write(")");
}
 
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
// Please refer below article for details of this
// function
// https://goo.gl/k6EYKj
static void matrixChainOrder(int []p, int n)
{
     
    /*
    * For simplicity of the program,
    one extra row and one extra column are
    * allocated in m[,]. 0th row and
    0th column of m[,] are not used
    */
    int[,] m = new int[n, n];
     
    // bracket[i,j] stores optimal break point in
    // subexpression from i to j.
    int[,] bracket = new int[n, n];
     
    /*
    * m[i,j] = Minimum number of scalar
    multiplications needed to compute the
    * matrix A[i]A[i+1]...A[j] = A[i..j] where
    dimension of A[i] is p[i-1] x p[i]
    */
     
    // cost is zero when multiplying one matrix.
    for(int i = 1; i < n; i++)
        m[i, i] = 0;
     
    // L is chain length.
    for(int L = 2; L < n; L++)
    {
        for(int i = 1; i < n - L + 1; i++)
        {
            int j = i + L - 1;
            m[i, j] = int.MaxValue;
            for (int k = i; k <= j - 1; k++)
            {
                 
                // q = cost/scalar multiplications
                int q = m[i, k] + m[k + 1, j] +
                       p[i - 1] * p[k] * p[j];
                        
                if (q < m[i, j])
                {
                    m[i, j] = q;
                     
                    // Each entry bracket[i,j]=k shows
                    // where to split the product arr
                    // i,i+1....j for the minimum cost.
                    bracket[i, j] = k;
                }
            }
        }
    }
 
    // The first matrix is printed as 'A', next as 'B',
    // and so on
    name = 'A';
    Console.Write("Optimal Parenthesization is : ");
    printParenthesis(1, n - 1, n, bracket);
    Console.Write("\nOptimal Cost is : " + m[1, n - 1]);
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 40, 20, 30, 10, 30 };
    int n = arr.Length;
     
    matrixChainOrder(arr, n);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// javascript program to print optimal parenthesization
// in matrix chain multiplication.
 
  var name=0;
 
  // Function for printing the optimal
  // parenthesization of a matrix chain product
  function printParenthesis(i , j, n, bracket)
  {
     
    // If only one matrix left in current segment
    if (i == j)
    {
      document.write(name++);
      return;
    }
    document.write("(");
 
    // Recursively put brackets around subexpression
    // from i to bracket[i][j].
    // Note that "*((bracket+i*n)+j)" is similar to
    // bracket[i][j]
    printParenthesis(i, bracket[i][j], n, bracket);
 
    // Recursively put brackets around subexpression
    // from bracket[i][j] + 1 to j.
    printParenthesis(bracket[i][j] + 1, j, n, bracket);
    document.write(")");
  }
 
  // Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
  // Please refer below article for details of this
  // function
  // https://goo.gl/k6EYKj
  function matrixChainOrder( p , n)
  {
    /*
         * For simplicity of the program,
         one extra row and one extra column are
         * allocated in m. 0th row and
         0th column of m are not used
         */
    var m = Array(n).fill(0).map(x => Array(n).fill(0));
 
    // bracket[i][j] stores optimal break point in
    // subexpression from i to j.
    var bracket = Array(n).fill(0).map(x => Array(n).fill(0));
 
    /*
         * m[i,j] = Minimum number of scalar
         multiplications needed to compute the
         * matrix A[i]A[i+1]...A[j] = A[i..j] where
         dimension of A[i] is p[i-1] x p[i]
         */
 
    // cost is zero when multiplying one matrix.
    for (var i = 1; i < n; i++)
      m[i][i] = 0;
 
    // L is chain length.
    for (var L = 2; L < n; L++)
    {
      for (var i = 1; i < n - L + 1; i++)
      {
        var j = i + L - 1;
        m[i][j] = Number.MAX_VALUE;
        for (var k = i; k <= j - 1; k++)
        {
 
          // q = cost/scalar multiplications
          var q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
          if (q < m[i][j])
          {
            m[i][j] = q;
 
            // Each entry bracket[i,j]=k shows
            // where to split the product arr
            // i,i+1....j for the minimum cost.
            bracket[i][j] = k;
          }
        }
      }
    }
 
    // The first matrix is printed as 'A', next as 'B',
    // and so on
    name = 'A';
    document.write("Optimal Parenthesization is : ");
    printParenthesis(1, n - 1, n, bracket);
    document.write("\nOptimal Cost is : " + m[1][n - 1]);
  }
 
  // Driver code
  var arr = [ 40, 20, 30, 10, 30 ];
  var n = arr.length;
  matrixChainOrder(arr, n);
 
// This code is contributed by 29AjayKumar
</script>
Producción

Optimal Parenthesization is : ((A(BC))D)nOptimal Cost is : 26000

Complejidad de Tiempo: O(n 3
Espacio Auxiliar: O(n 2 )

Otro enfoque:

Esta solución intenta resolver el problema usando recursividad usando permutaciones.

Let's take example:  {40, 20, 30, 10, 30}
n = 5

Vamos a dividir eso en una Matrix

[ [40, 20], [20, 30], [30, 10], [10, 30] ]

[ A , B , C , D ]

it contains 4 matrices i.e. (n - 1)

Tenemos 3 combinaciones para multiplicar es decir (n-2)

AB    or    BC    or     CD

Algoritmo:

1) Dada la array de arrays con longitud M, bucle a través de M – 1 veces

2) Combinar arrays consecutivas en cada ciclo

for (int i = 0; i < M - 1; i++) {
   int cost =  (matrices[i][0] * 
                 matrices[i][1] * matrices[i+1][1]);
   
   // STEP - 3
   // STEP - 4
}

3) Combinar las dos arrays actuales en una y eliminar la lista de arrays combinadas de la lista.

If  A, B merged, then A, B must be removed from the List

and NEW matrix list will be like
newMatrices = [  AB,  C ,  D ]

We have now 3 matrices, in any loop
Loop#1:  [ AB,  C,   D ]
Loop#2:  [ A,   BC,  D ]
Loop#3   [ A,   B,   CD ]

4) Repita: Vaya al PASO – 1 con   newArrays como entrada M – recursividad

5) Detener la recursión, cuando tengamos 2 arrays en la lista.

flujo de trabajo

Las arrays se reducen de la siguiente manera, 

y los costos deben conservarse y resumirse durante la recursividad con los valores anteriores de cada paso principal.

[ A, B , C, D ]

[(AB), C, D ]
 [ ((AB)C), D ]--> [ (((AB)C)D) ] 
 - return & sum-up total cost of this step.
 [ (AB),  (CD)] --> [ ((AB)(CD)) ] 
 - return .. ditto..

 [ A, (BC), D ]
 [ (A(BC)), D ]--> [ ((A(BC))D) ] 
  - return
 [ A, ((BC)D) ]--> [ (A((BC)D)) ] 
  - return
    
 [ A, B, (CD) ]
 [ A, (B(CD)) ]--> [ (A(B(CD))) ] 
  - return
 [ (AB), (CD) ]--> [ ((AB)(CD)) ] 
  - return .. ditto..

a la vuelta, es decir, al paso final de cada recursión, compruebe si este valor es menor que el de cualquier otro.

A continuación se muestra la implementación JAVA de los pasos anteriores.

Java

import java.util.Arrays;
 
public class MatrixMultiplyCost {
 
    static class FinalCost
    {
        public String label = "";
        public int cost = Integer.MAX_VALUE;
    }
 
    private void optimalCost(int[][] matrices,
                             String[] labels, int prevCost,
                             FinalCost finalCost)
    {
        int len = matrices.length;
 
        if (len < 2)
        {
            finalCost.cost = 0;
            return;
        }
        else if (len == 2)
        {
            int cost = prevCost
                       + (matrices[0][0] *
                          matrices[0][1] *
                          matrices[1][1]);
 
            // This is where minimal cost has been caught
            // for whole program
            if (cost < finalCost.cost)
            {
                finalCost.cost = cost;
                finalCost.label
                    = "(" + labels[0]
                    + labels[1] + ")";
            }
            return;
        }
 
        // recursive Reduce
        for (int i = 0; i < len - 1; i++)
        {
            int j;
            int[][] newMatrix = new int[len - 1][2];
            String[] newLabels = new String[len - 1];
            int subIndex = 0;
 
            // STEP-1:
            //   - Merge two matrices's into one - in each
            //   loop, you move merge position
            //        - if i = 0 THEN  (AB) C D ...
            //        - if i = 1 THEN  A (BC) D ...
            //        - if i = 2 THEN  A B (CD) ...
            //   - and find the cost of this two matrices
            //   multiplication
            int cost = (matrices[i][0] * matrices[i][1]
                        * matrices[i + 1][1]);
 
            // STEP - 2:
            //    - Build new matrices after merge
            //    - Keep track of the merged labels too
            for (j = 0; j < i; j++) {
                newMatrix[subIndex] = matrices[j];
                newLabels[subIndex++] = labels[j];
            }
 
            newMatrix[subIndex][0] = matrices[i][0];
            newMatrix[subIndex][1] = matrices[i + 1][1];
            newLabels[subIndex++]
                = "(" + labels[i] + labels[i + 1] + ")";
 
            for (j = i + 2; j < len; j++) {
                newMatrix[subIndex] = matrices[j];
                newLabels[subIndex++] = labels[j];
            }
 
            optimalCost(newMatrix, newLabels,
                        prevCost + cost, finalCost);
        }
    }
 
    public FinalCost findOptionalCost(int[] arr)
    {
        // STEP -1 : Prepare and convert inout as Matrix
        int[][] matrices = new int[arr.length - 1][2];
        String[] labels = new String[arr.length - 1];
 
        for (int i = 0; i < arr.length - 1; i++) {
            matrices[i][0] = arr[i];
            matrices[i][1] = arr[i + 1];
            labels[i] = Character.toString((char)(65 + i));
        }
        printMatrix(matrices);
 
        FinalCost finalCost = new FinalCost();
        optimalCost(matrices, labels, 0, finalCost);
 
        return finalCost;
    }
 
    /**
     * Driver Code
     */
    public static void main(String[] args)
    {
        MatrixMultiplyCost calc = new MatrixMultiplyCost();
 
        // ======= *** TEST CASES **** ============
 
        int[] arr = { 40, 20, 30, 10, 30 };
        FinalCost cost = calc.findOptionalCost(arr);
        System.out.println("Final labels: \n" + cost.label);
        System.out.println("Final Cost:\n" + cost.cost
                           + "\n");
    }
 
    /**
     * Ignore this method
     * - THIS IS for DISPLAY purpose only
     */
    private static void printMatrix(int[][] matrices)
    {
        System.out.print("matrices = \n[");
        for (int[] row : matrices) {
            System.out.print(Arrays.toString(row) + " ");
        }
        System.out.println("]");
    }
}
 
// This code is contributed by suvera
Producción

arrays = 
[[40, 20] [20, 30] [30, 10] [10, 30] ]
Final labels: 
((A(BC))D)
Final Cost:
26000

Este artículo es una contribución de Yasin Zafar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *