Skip to content

Instantly share code, notes, and snippets.

@Said210

Said210/matrixMut.html

Created June 15, 2021 17:50
Show Gist options
  • Save Said210/0f64f214a186e5db386029841a802c84 to your computer and use it in GitHub Desktop.
Save Said210/0f64f214a186e5db386029841a802c84 to your computer and use it in GitHub Desktop.
Download ZIP
chain matrix multiplication algorithm using dynamic programming.
Raw
matrixMut.html
<!DOCTYPE html>
<html>
<head>
<title>Multiplicación de matrices.</title>
<meta charset="UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<link href="https://unpkg.com/tailwindcss@^2/dist/tailwind.min.css" rel="stylesheet" type="text/css" />
<link rel="stylesheet" href="https://pro.fontawesome.com/releases/v5.10.0/css/all.css" integrity="sha384-AYmEC3Yw5cVb3ZcuHtOA93w35dYTsvhLPVnYs9eStHfGJvOvKxVfELGroGkvsg+p" crossorigin="anonymous"/>
<style type="text/css">
body{background-color: #F9FAFB;}
.card{background-color: #fff;}
.text-violet{ color: #D8B4FE;}
input[disabled]{ background-color: #F0F0F0; }
td{border: 1px solid #ccc; }
.optimal_sol{color: rgb(40,160,30)}
</style>
</head>
<body>
<div class="w-full" id="app">
<div class="grid grid-flow-col grid-cols-5">
<div class="col-start-2 col-end-5 card rounded-md p-5 my-5">
<h1 class="text-3xl text-violet text-center">Calculador de multiplicación de matriz.</h1>
<p class="text-l text-center"> Calculadora con programación dínamica para generar la forma óptima de multiplicar matrices. </p>
<br><br>
</div>
<div class="col-start-2 col-end-5 card rounded-md p-5 my-2">
<p class="text-center">Por favor ingresa la cantidadad de matrices.</p>
<div class="relative flex w-full flex-wrap items-stretch mb-3 mt-4">
<input v-model="num_of_matrix" type="number" placeholder="3" class="px-3 py-3 placeholder-blueGray-300 text-blueGray-600 relative bg-white bg-white rounded text-sm border-0 shadow outline-none focus:outline-none focus:ring w-full pr-10"/>
<span class="z-10 h-full leading-snug font-normal absolute text-center text-blueGray-300 absolute bg-transparent rounded text-base items-center justify-center w-8 right-0 pr-3 py-3">
<i class="fas fa-table"></i>
</span>
</div>
<button v-on:click="set_num_of_matrixes" class="bg-pink-400 text-white hover:bg-pink-500 font-bold uppercase text-sm px-6 py-3 rounded-full hover:shadow outline-none focus:outline-none ease-linear transition-all duration-100" type="button" style="margin-left: 50%; transform: translateX(-50%);">
Siguiente
</button>
</div>
<matrix-input-item
v-for="(mat, i) in matrixes"
v-bind:matrix_number="i"
v-bind:locked="i >= 1"
v-bind:past_h="(i >= 1) ? matrixes[i-1] : 0"
v-bind:is_last="i == matrixes.length - 1"></matrix-input-item>
<div class="col-start-2 col-end-5 card rounded-md p-5 my-5">
Tabla de resultados.
<table id="result_table"></table>
</div>
</div>
</div>
<script src="https://cdn.jsdelivr.net/npm/vue/dist/vue.js"></script>
<script type="text/javascript">
Vue.component('matrix-input-item', {
props: ['matrix_number', 'locked', 'past_h', 'is_last'],
template: `<div v-bind:id="'matrix_input_' + matrix_number" class="col-start-2 col-end-5 card rounded-md p-5 my-2" v-bind:style="'animation-delay: ' + matrix_number*100 + 'ms' ">
<p class="text-center mb-5">Ingresa el tamaño de la matriz (#{{matrix_number}}):</p>
<div class="flex flex-wrap">
<div class="w-1/2">
Ancho: <br>
<input v-if="!locked" v-bind:id="'matrix_' + matrix_number" type="text" placeholder="1" class="px-3 py-3 placeholder-blueGray-300 text-blueGray-600 relative bg-white bg-white rounded text-sm border-0 shadow outline-none focus:outline-none focus:ring w-5/6 pr-10"/>
<input v-if="locked" v-bind:id="'matrix_locked_' + matrix_number" disabled type="text" v-bind:value="past_h" class="px-3 py-3 placeholder-blueGray-300 text-blueGray-600 relative bg-white bg-white rounded text-sm border-0 shadow outline-none focus:outline-none focus:ring w-5/6 pr-10"/>
</div>
<div class="w-1/2">
Alto: <br>
<input onkeyup="app.update_render()" v-bind:id="'matrix_' + (matrix_number + 1)" type="text" placeholder="4" class="px-3 py-3 placeholder-blueGray-300 text-blueGray-600 relative bg-white bg-white rounded text-sm border-0 shadow outline-none focus:outline-none focus:ring w-5/6 pr-10"/>
</div>
</div>
<button v-if="is_last" onclick="app.render_table()" class="bg-pink-400 text-white hover:bg-pink-500 font-bold uppercase text-sm mt-2 px-6 py-3 rounded-full hover:shadow outline-none focus:outline-none ease-linear transition-all duration-100" type="button" style="margin-left: 50%; transform: translateX(-50%);">
Calcular
</button>
</div>`
})
var app = new Vue({
el: '#app',
data: {
status: 0,
num_of_matrix: 0,
matrixes: [],
solution_matrix: []
},
methods: {
set_num_of_matrixes: function(){
num_of_matrix = parseInt(this.num_of_matrix);
if(num_of_matrix <= 0){return false;}
for(var i = 0; i < num_of_matrix; i++){
this.matrixes[i] = 0;
}
app.$forceUpdate();
},
render_table: function(){
var serialized_values = [];
for(var i = 0; i <= this.num_of_matrix; i++){
serialized_values.push(parseInt(document.getElementById("matrix_" + i).value));
}
console.log(serialized_values);
let res = MatrixChainOrder(serialized_values, serialized_values.length);
let optimal = res[2];
let optimal_matrix = res[0];
let full_matrix = res[1];
let render = "";
for(var i = 1; i < full_matrix.length; i++){
render += "<tr>";
for(var j = 1; j < full_matrix[i].length; j++){
if( Number.isInteger(full_matrix[i][j]) ){
render += "<td>" + full_matrix[i][j] +"</td>";
}else{
render += "<td>";
for(var k = 0; k < full_matrix[i][j].length; k++){
if(("" + full_matrix[i][j][k]).indexOf(optimal_matrix[i][j] + "") != -1){
render += "<b class=" + ((optimal_matrix[i][j] == optimal) ? 'optimal_sol' : '') + ">" + full_matrix[i][j][k] + "</b><br><br>";
}else{
render += full_matrix[i][j][k] + "<br><br>";
}
}
render += "</td>";
}
}
render += "</tr>"
}
document.getElementById("result_table").innerHTML = render;
},
update_render: function(){
var locked_index = 1;
for(var i = 0; i <= this.num_of_matrix; i++){
if(i > 1 ){
let prev_val = pv = document.getElementById("matrix_"+(i-1)).value;
document.getElementById("matrix_locked_"+locked_index).value = prev_val;
locked_index++;
}
}
app.$forceUpdate();
}
}
})
/*
Recibe las dimesiones serializadas de las matrices
Por ejemplo
[MxN] [NxQ] [QxR] = [M, N, Q, R]
*/
function MatrixChainOrder(p , n){
/*POR SIMPLICIDAD se agrega una columa y filas extra en la pos 0 que no son usadas.*/
var m = Array(n).fill(0).map(x => Array(n).fill(0));
// Guardar
var op = Array(n).fill(0).map(x => Array(n).fill(0));
var i, j, k, L, q;
/* m[i, j] = Minimo numero de operaciones
multiplicaciones necesarias
A[i]A[i+1]...A[j] = A[i..j] donde
es dimensión de A[i] que es p[i-1] x p[i] */
// si solo es una matriz el costo es 0
for (i = 1; i < n; i++)
m[i][i] = 0;
// L ees el largo de la cadena.
for (L = 2; L < n; L++)
{
for (i = 1; i < n - L + 1; i++)
{
j = i + L - 1;
if (j == n)
continue;
m[i][j] = Number.MAX_VALUE;
for (k = i; k <= j - 1; k++)
{
// q = cost/scalar multiplications
q = m[i][k] + m[k + 1][j]
+ p[i - 1] * p[k] * p[j];
let desc = m[i][k] + " + " + m[k+1][j] + " + (" + p[i-1] + " * " + p[k] + " * " + p[j] + ")";
if(op[i][j] == 0){
op[i][j] = [desc + ": " + q]
}else{
op[i][j].push(desc + ": " + q);
}
if (q < m[i][j])
m[i][j] = q;
}
}
}
console.table(m)
console.table(op)
// return m[1][n - 1];
return [m, op, m[1][n - 1]]
}
// Driver code
var arr = [ 30, 1, 40, 10, 25 ];
var size = arr.length;
// document.write(
// "Minimum number of multiplications is "
// + MatrixChainOrder(arr, size));
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment