P2 MatrixChain

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author ArCiGo
 */
public class matrixChain {

    public static int[][] matrixChainM(int[] r, int[][] m, int[][] s) {

        int n;              /*longitud del arreglo - 1*/
        int i, l, k;        /*indices de los ciclos*/
        int j, q;           /*guarda las operaciones*/
        int infinity = 1000000;

        n = r.length;

        for (i = 1; i < n; i++) {
            m[i][i] = 0;
        }
        for (l = 2; l < n; l++) {
            for (i = 1; i < (n - l + 1); i++) {
                j = i + l - 1;
                m[i][j] = infinity;
                for (k = i; k <= (j - 1); k++) {
                    q = m[i][k] + m[k + 1][j] + r[i - 1] * r[k] * r[j];
                    if (q < m[i][j]) {
                        m[i][j] = q;
                        s[i][j] = k;
                    }
                }
            }
        }
        return m;
    }

    public static int[][] matrixChainS(int[] r, int[][] m, int[][] s) {

        int n;              /*longitud del arreglo - 1*/
        int i, l, k;        /*indices de los ciclos*/
        int j, q;           /*guarda las operaciones*/
        int infinity = 1000000;

        n = r.length;

        for (i = 1; i < n; i++) {
            m[i][i] = 0;
        }
        for (l = 2; l < n; l++) {
            for (i = 1; i < (n - l + 1); i++) {
                j = i + l - 1;
                m[i][j] = infinity;
                for (k = i; k <= (j - 1); k++) {
                    q = m[i][k] + m[k + 1][j] + r[i - 1] * r[k] * r[j];
                    if (q < m[i][j]) {
                        m[i][j] = q;
                        s[i][j] = k;
                    }
                }
            }
        }
        return s;
    }

    public static int matrixChainMultiplication(int[] v, int[][] s, int i, int j) {

        int x, y;

        if (j < i) {
            x = matrixChainMultiplication(v, s, i, s[i][j]);
            y = matrixChainMultiplication(v, s, s[i][j] + 1, j);
            return x * y;
        } else {
            return v[i];
        }
    }

    public static void matrixChainParentization(int[][] s, int i, int j){

        if(i==j){
            System.out.print("A"+i);
        }
        else{
            System.out.print("(");
            matrixChainParentization(s, i, s[i][j]);
            matrixChainParentization(s, s[i][j] + 1, j);
            System.out.print(")");
        }
    }

    public static int[][] matrixMultiplication(int[][] x, int[][] y) {

        int[][] z = new int[x.length][y.length];
        int acum;

        for (int i = 0; i < x.length; i++) {
            for (int j = 0; j < y.length; j++) {
                acum = 0;
                for (int k = 0; k < z.length; k++) {
                    acum += (x[i][k] * y[k][j]);
                }
                z[i][j] = acum;
            }
        }
        return z;
    }

    public static void main(String[] args) {

        int r[] = {3, 2, 4, 1};
        int m[][] = new int[4][4];
        int s[][] = new int[4][4];

        int v;

        System.out.println("Matriz m");
        m = matrixChainM(r, m, s);
        for (int i = 1; i < m.length; i++) {
            for (int j = 1; j < m.length; j++) {
                System.out.print(" " + m[i][j] + " ");
            }
            System.out.println("");
        }

        System.out.println("Matriz s");
        s = matrixChainS(r, m, s);
        for (int i = 1; i < s.length; i++) {
            for (int j = 1; j < s.length; j++) {
                System.out.print(" " + s[i][j] + " ");
            }
            System.out.println("");
        }

        v = matrixChainMultiplication(r, s, 1, 6);
        System.out.println("Menor número de multiplicaciones: " + v);

        System.out.println("Parentsesizacion: ");
        matrixChainParentization(s,1,3);
    }
}