(* ESIM 2002 *) (* Permutation et arbre binaire croissant *) let pi =[|7;2;4;6;3;5;1|] ;; type arbre = nil | noeud of arbre * int * arbre ;; let construire_arbre t = let rec indice_minimum i j = if i=j then i else let k=indice_minimum (i+1) j in if t.(i) < t.(k) then i else k in let rec construit_aux i j = if i > j then nil else if i=j then noeud(nil,t.(i),nil) else let k = indice_minimum i j in noeud(construit_aux i (k-1), t.(k), construit_aux (k+1) j) in construit_aux 0 (vect_length t -1) ;; let rec affiche_arbre a = match a with | nil -> () | noeud(ag,r,ad) -> affiche_arbre ag; print_int r; print_char `;`; affiche_arbre ad ;; (* Tableaux de Young *) let maxint = int_of_float(2.**30.-.1.);; let nmax = 10 ;; let m = make_matrix nmax nmax maxint ;; let init () = let t = make_matrix nmax nmax maxint in for j=0 to (nmax-1) do t.(0).(j) <- 0 done ; for i=1 to (nmax-1) do t.(i).(0) <- 0 done ; t;; m = init();; m.(1).(1) <- 1 ;; m.(1).(2) <- 3 ;; m.(1).(3) <- 9 ;; m.(1).(4) <-16 ;; m.(2).(1) <- 2 ;; m.(2).(2) <- 6 ;; m.(2).(3) <- 10;; m.(3).(1) <- 4 ;; m.(3).(2) <- 11;; m.(3).(3) <- 12;; m.(4).(1) <- 13 ;; m.(4).(2) <- 14 ;; m.(5).(1) <- 19 ;; let affiche t = let i = ref 1 and j = ref 1 in while t.(!i).(1) < maxint do j:=1; while t.(!i).(!j) < maxint do print_int t.(!i).(!j); print_char`;`; j := !j + 1; done; print_newline(); i := !i +1; done ;; let est_de_young t = let i = ref 1 and j = ref 1 and ok = ref true in while !ok && t.(!i).(1) < maxint do j:=1; while !ok && t.(!i).(!j) < maxint do if t.(!i).(!j)>t.(!i).(!j+1) || t.(!i).(!j)>t.(!i+1).(!j) then ok := false; j := !j +1 done; i := !i +1 done; !ok ;; let insere elmt t = let j = ref 1 in let rec aux i x = j := 1; while x > t.(i).(!j) do j := !j + 1 done; let y = t.(i).(!j) in t.(i).(!j) <- x; if y = maxint then (i,!j) else aux (i+1) y in aux 1 elmt ;; let young_of_vect pi = let t = init () in for i = 0 to (vect_length pi - 1) do let(x,y) = insere pi.(i) t in () done; t ;; let supprime x y t = let e = ref t.(x).(y) and i =ref (x-1) and j = ref y in t.(x).(y) <- maxint; while !i > 0 do while t.(!i).(!j) < !e do j := !j +1 done; j := !j -1; let ee = t.(!i).(!j) in t.(!i).(!j) <- !e; e := ee; i := !i-1; done; !e;; let supprime_coin t = let e = t.(1).(1) and x = ref t.(2).(1) and i= ref 1 and j = ref 1 in while t.(!i).(1) < maxint do j := 1; while !x > t.(!i).(!j+1) do t.(!i).(!j) <- t.(!i).(!j+1); j := !j + 1; done; t.(!i).(!j) <- !x; i := !i + 1; x := t.(!i+1).(1); done; e ;; let tri v = let n = vect_length v and t = init () in for i=0 to n-1 do let x = insere v.(i) t in () done; for i=0 to n-1 do v.(i) <- supprime_coin t; done; v ;; let robinson pi = let p = init() and q = init() in for i = 0 to vect_length pi -1 do let (x,y) = insere pi.(i) p in q.(x).(y) <- i + 1 done; (p,q) ;; let robinson_inverse (p,q) = let taille t = let i = ref 1 and j = ref 1 and lg = ref 0 in while t.(!i).(1) < maxint do j:=1; while t.(!i).(!j) < maxint do lg := !lg + 1; j := !j + 1; done; i := !i +1; done; !lg and cherche k t = let i = ref 1 and j = ref 1 and trouve = ref false in while not(!trouve) && t.(!i).(1) < maxint do j:=1; while not(!trouve) && t.(!i).(!j) < maxint do if t.(!i).(!j) = k then trouve := true; j := !j +1 done; i := !i +1 done; (!i-1,!j-1) in let n = taille p in let pi = make_vect n 0 in for k = 0 to n-1 do let (x,y) = cherche (k+1) q in pi.(k) <- supprime x y p done; pi ;; let produit_equerres t = let longueur_equerre i j = let s = ref 1 and k = ref(i+1) and l = ref(j+1) in while t.(i).(!k) < maxint do s := !s + 1; k := !k + 1 done; while t.(!l).(j) < maxint do s := !s + 1; l := !l + 1 done; !s ; in let p= ref 1 and i = ref 1 and j = ref 1 in while t.(!i).(1) < maxint do j:=1; while t.(!i).(!j) < maxint do p := !p * (longueur_equerre !i !j) ; j := !j + 1; done; i := !i +1; done; !p ;;