Random.self_init ();;

let estDerangement d = let n = Array.length d and out=ref true in
	for i=0 to (n-1)
	do
		out := !out && (not (i=d.(i)))
	done;
	!out;;
	
let asCocopain d = let n = Array.length d and out=ref false in
	for i=0 to (n-1)
	do
		out := !out || (i=d.(d.(i)))
	done;
	!out;;
	
let randPerm n = let out = Array.make n (-1) in
	for i=0 to (n-1)
	do
		let dest= ref (Random.int n) in
		while not (out.(!dest)=(-1))
		do dest := (!dest +1) mod n
		done;
		out.(!dest) <- i
	done;
	out;;
let stat l total =
	let rec aux l = match l with
		| [] -> 0.,0.,0
		| e::s -> let r = (float_of_int e)/.(float_of_int total) in
			let (sum,scar,n)=aux s in (sum+.r,scar+.(r*.r),n+1) 
	in
	let (sum,scar,n)=aux l in
	let moy = sum /. (float_of_int n) in
	let var = (scar /. (float_of_int n)) -. moy*.moy in
		(moy,sqrt var);;
		
let rec sum l = match l with
	| [] -> 0
	| e::s -> e+(sum s);;


let printstat l t total = 
	let moy,ec = stat l total in
		print_string "Proportions de ";
		print_string t;
		print_string " : ";
		print_float moy;
		print_string " (écart type: ";
		print_float ec;
		print_endline ")";;

let time f =
	let t = Sys.time () in
	let x = f () in
	Printf.printf "Executé en %fs\n" (Sys.time() -. t);
	x;;

let n = 33;;
let tests = 10000;;
let echz = 18000;;
let derang = ref 0;;
let dermoy = ref [];;
let dertot = ref 0;;
let cocopain = ref 0;;
let cocomoys = ref [];;
let t0 = Sys.time() in
for ech=1 to echz
do
for i=1 to tests
do
	let d = randPerm n in
	if estDerangement d
	then begin
		derang := !derang +1;
		if asCocopain d
		then (cocopain := !cocopain + 1)
	end
done;
dermoy   :=   (!derang)::!dermoy;
dertot   :=   (!derang)+(!dertot);
cocomoys := (!cocopain)::!cocomoys;
derang := 0;
cocopain := 0;
Random.self_init ();
print_endline (string_of_int ech);
done;
print_string "Temps d'éxecution: ";
print_endline (string_of_float (Sys.time() -. t0));;
let derag = sum !dermoy;;
printstat (!dermoy) "dérangements" tests;;
printstat (!cocomoys) "cocopains" (derag/echz);;
dertot;;