(* Mélange de Knuth : comment mélanger les éléments d'un tableau de
   façon parfaite (i.e. équitable parmi les n! permutations) et
   efficacement (i.e. en temps linéaire). *)

let swap a i j =
  let t = a.(i) in a.(i) <- a.(j); a.(j) <- t

let knuth_shuffle a =
  for i = 1 to Array.length a - 1 do
    let j = Random.int (i + 1) in (* entre 0 et i inclus *)
    swap a i j
  done

(* petit test : on mélange plein de fois un tableau contenant initialement
   0..m-1 et on compte le nombre de fois que la valeur i se retrouve au
   final dans la case j, puis on affiche le nombre moyen pour chaque couple
   (i,j), qui doit être proche de 1/m. *)

let m = 10
let a = Array.init m (fun i -> i)
let occ = Array.make_matrix m m 0
let steps = 1_000_000
let () =
  for k = 1 to steps do
    for i = 0 to m - 1 do a.(i) <- i done;
    knuth_shuffle a;
    for i = 0 to m - 1 do let v = a.(i) in occ.(v).(i) <- occ.(v).(i) + 1 done
  done;
  for v = 0 to m - 1 do
    for i = 0 to m - 1 do
      Printf.printf "%.3f " (float occ.(v).(i) /. float steps)
    done;
    Printf.printf "\n"
  done

This document was generated using caml2html