Sys.command "ocaml -version";;

type mot = int array ;;

let est_permut (m : mot) : bool =
  let p = Array.length m in
  let permut_bool = ref true in
  let i = ref 0 in
  while !i<p && !permut_bool do
    permut_bool := !permut_bool && ( Array.exists (fun x -> x = !i) m );
    incr i
  done;
  !permut_bool;;
(* Complexité temporelle au pire en O(p^2) *)
(* Complexité spatiale en O(p) *)

est_permut [|3; 5; 1; 2; 4; 0|];; (* true ! *)
est_permut [|3; 5; 1; 3; 4; 0|];; (* false ! il manque le 2, il y a deux fois le 3 *)

let est_permut_lineaire (m : mot) : bool =
  let p = Array.length m in
  let tous_vus = Array.make p false in
  Array.iter (fun mi ->
    tous_vus.(mi) <- true
  ) m;
  Array.for_all (fun b -> b) tous_vus
;;
(* Complexité temporelle au pire en O(p) *)
(* Complexité spatiale en O(p) *)

est_permut_lineaire [|3; 5; 1; 2; 4; 0|];; (* true ! *)
est_permut_lineaire [|3; 5; 1; 3; 4; 0|];; (* false ! il manque le 2, il y a deux fois le 3 *)

let echange t i j =
  let tmp = t.(i) in
  t.(i) <- t.(j);
  t.(j) <- tmp;
;;

Random.self_init ();;

let permutation_aleatoire p =
  let m = Array.init p (fun i -> i) in
  for _ = 1 to Random.int (10*p) do
    echange m (Random.int p) (Random.int p);
  done;
  m
;;

permutation_aleatoire 10;;

permutation_aleatoire 10;;

permutation_aleatoire 10;;

let timeit f () =
  let debut = Sys.time () in
  let res = f () in
  let fin = Sys.time () in
  Printf.printf "\nTemps pour calculer f() = %f seconde(s)." (fin -. debut);
  res
;;

let test f_est_permut nombre_test taille () =
  Printf.printf "\nDébut de %i tests de taille %i..." nombre_test taille;
  flush_all ();
  for _ = 1 to nombre_test do
    let m = permutation_aleatoire taille in
    assert (f_est_permut m);
  done
;;

timeit (test est_permut_lineaire 100 1000) ();;
timeit (test est_permut_lineaire 100 2000) ();;
timeit (test est_permut_lineaire 100 4000) ();;

Printf.printf "\n\n\n";;
flush_all();;

timeit (test est_permut 100 1000) ();;
timeit (test est_permut 100 2000) ();;
timeit (test est_permut 100 4000) ();;

Printf.printf "\n\n\n";;
flush_all();;

let trouve_omega (m : mot) : mot =
  let p = Array.length m in
  let omega = Array.make p 0 in
  for i=0 to (p-1) do
    omega.(i) <- (i + m.(i)) mod p
  done;
  omega;;

trouve_omega [|4;4;1|];;
trouve_omega [|5;3;4;0|];;

Array.make;;
Array.init;;

let trouve_omega (m : mot) : mot =
  let p = Array.length m in
  Array.init p (fun i -> ((i + m.(i)) mod p))
;;

trouve_omega [|4;4;1|];;
trouve_omega [|5;3;4;0|];;

let entier (s : char) : int = match s with
  | '0'-> 0
  | '1'-> 1
  | '2'-> 2
  | '3'-> 3
  | '4'-> 4
  | '5'-> 5
  | '6'-> 6
  | '7'-> 7
  | '8'-> 8
  | '9'-> 9
;;

let entier (s : char) : int =
  (int_of_char s) - (int_of_char '0')
;;

let transfo_mot (m : string) : mot =
  let p = String.length m in
  let mot_tableau = Array.make p 0 in
  for i = 0 to (p - 1) do
    mot_tableau.(i) <- entier (m.[i])
  done;
  mot_tableau;;
(* Complexité temporelle et spatiale en O(p) *)

transfo_mot "5241";;

Array.init

let transfo_mot (m : string) : mot =
  Array.init (String.length m) (fun i -> (entier m.[i]))
(* Complexité temporelle et spatiale en O(p) *)

transfo_mot "5241";;

let test_permut (m : string) : bool =
  est_permut (trouve_omega (transfo_mot m));;
(* Complexité temporelle en O(p) *)

let test_permut_mot (m : mot) : bool =
  est_permut (trouve_omega m);;
(* Complexité temporelle en O(p) *)

test_permut "433";; (* pas jonglable *)

test_permut "432";; (* pas jonglable *)

test_permut "441";; (* jonglable *)

test_permut "5241";; (* jonglable *)

test_permut "9340";; (* jonglable *)

let test_moyenne_mot (m : mot) (b : int) : bool =
  let p = Array.length m in
  let s = ref 0 in
  for i = 0 to (p - 1) do
    s:= !s + m.(i)
  done;
  !s / p = b (* on teste l'égalité *)
;;

test_moyenne_mot [|5;4;3;0|] 3;;

let test_moyenne (m : string) (b : int) : bool =
  test_moyenne_mot (transfo_mot m) b;;

test_moyenne "433" 3;;

test_moyenne "443" 3;;

test_moyenne "432" 3;;

test_moyenne "5430" 3;;

let rec partition_aux balles p debut somme acc =
  let m = balles * p in
  let manque = Array.fold_left (fun c x -> if x = (-1) then c + 1 else c) 0 debut in
  if manque = 1 then
    let t = Array.copy debut in
    t.(p - 1) <- m - somme;
    t :: acc
  else
    let nacc = ref acc in
    for k = m - somme downto 0 do
      let ndebut = Array.copy debut in
      ndebut.(p - manque) <- k;
      nacc := partition_aux balles p ndebut (somme + k) !nacc
    done;
    !nacc
;;

let partition balles p =
  let debut = Array.make p (-1) in
  partition_aux balles p debut 0 []
;;

let bp balles p = List.filter test_permut_mot (partition balles p);;

partition 3 3;;

bp 3 3;;

List.mem [|4; 4; 1|] (bp 3 3);;
List.mem [|4; 2; 3|] (bp 3 3);;
List.mem [|3; 3; 3|] (bp 3 3);;

List.mem [|4; 3; 3|] (bp 3 3);;


partition 4 4;;

List.length (partition 4 4);;

bp 4 4;;

List.length (bp 4 4);;