sous-sequence.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val aux_dyn : 'a array -> int array = <fun>\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int array = [|1; 2; 1; 2; 2; 3; 3; 4; 4; 3|]\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let aux_dyn s = \n",
    "    let n = Array.length s in \n",
    "    let longueurs = Array.make n 1 in\n",
    "    for c = 0 to n-1 do\n",
    "         let m = ref 1 in \n",
    "         let b = ref false in\n",
    "         for k = 0 to c-1 do\n",
    "            if s.(k)<= s.(c) then begin m := max (!m) longueurs.(k) ; b:= true end\n",
    "            done ; (* si on n'a pas changé m, on a 1 la bonne valeur déjà mise dans le tableau*)\n",
    "         if !b then longueurs.(c) <- 1+ !m \n",
    "    done ; longueurs ;;\n",
    "aux_dyn [|10;12;2;8;3;11;7;14;9;4|]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val l_seq_dyn : 'a array -> int = <fun>\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let l_seq_dyn s = let l = aux_dyn s in \n",
    "    let m = ref 0 in\n",
    "    for c = 0 to Array.length l -1 do\n",
    "        m := max (!m) l.(c)\n",
    "    done ; !m ;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val sous_sequence_dyn : int array -> int array = <fun>\n"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int array = [|2; 3; 7; 9|]\n"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let sous_sequence_dyn s = let l = aux_dyn s in \n",
    "    let a= (let m = ref 0 in\n",
    "    for c = 0 to Array.length l -1 do\n",
    "        m := max (!m) l.(c)\n",
    "    done ; !m ) in \n",
    "    let m = ref a in\n",
    "    let u = Array.make (!m) 0 in let j = ref (Array.length l -1) in let i = ref 0 in\n",
    "     while !m >0 do (* on va, voir si on a un m, si on l'a alors on ajoute le terme séquentiel correspondant dans u, on décrémente m, on a incrémente i l'indice de là où on ajoute dans u et on décrémente j qui est l'indice de la boucle*)\n",
    "     if l.(!j)=(!m) then\n",
    "     begin u.(a-1-(!i))<- s.((!j)) ; i:=!i+1 ; m:=!m-1 ; end ; j := !j-1  (* on a la partie finale qui est normale*)\n",
    "     done ; u ;;\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type config = int list array\n"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type config = int list array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val patience : 'a list -> 'a list array = <fun>\n"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int list array = [|[2; 5]; [2; 3; 8]; [9]; []; []; []|]\n"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let patience u =\n",
    "    let n = List.length u in let t = Array.make n [] in \n",
    "    let a = ref u in\n",
    "    while !a<>[] do\n",
    "        match !a with\n",
    "            |[]-> ()\n",
    "            |x::r ->  let c = ref 0 in let trouve = ref false in \n",
    "            while !c<n && not(!trouve) do\n",
    "               begin match t.((!c)) with\n",
    "                |[] -> t.(!c) <- [x] ; trouve := true\n",
    "                |m::q -> if x<m then begin t.(!c) <- x::m::q ; trouve := true end\n",
    "                end\n",
    "                ; c:= !c +1\n",
    "            done ; a := r \n",
    "    done ; t ;;\n",
    "            \n",
    "patience [5;2;8;9;3;2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val patience_opt : 'a list -> 'a list array = <fun>\n"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : int list array = [|[2; 5]; [2; 3; 8]; [9]; []; []; []|]\n"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec patience_opt u = \n",
    "    let n = List.length u in let t = Array.make n [] in \n",
    "    let a = ref u in\n",
    "    while !a<>[] do\n",
    "        match !a with\n",
    "            |[]-> ()\n",
    "            |x::r ->  let i = ref 0 in let j = ref n  in \n",
    "            while !j-(!i)>=1 do\n",
    "            let mid = (!i+(!j))/2 in\n",
    "               begin match t.(mid) with\n",
    "                |[] -> j:= mid\n",
    "                |m::q -> if x<m then begin j:=mid end else begin i:=mid +1 end\n",
    "                end\n",
    "            done ; t.(!j)<- x::t.(!j) ; a := r \n",
    "    done ; t ;;\n",
    "\n",
    "patience_opt [5;2;8;9;3;2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "OCaml 4.08.1+flambda",
   "language": "OCaml",
   "name": "ocaml-jupyter"
  },
  "language_info": {
   "codemirror_mode": "text/x-ocaml",
   "file_extension": ".ml",
   "mimetype": "text/x-ocaml",
   "name": "OCaml",
   "nbconverter_exporter": null,
   "pygments_lexer": "OCaml",
   "version": "4.08.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}