(*** Combinaisons d'une liste ***)

(* CONTRAT 
Fonction qui génère des combinaisons
Paramètre k : nombre d'objets que l'on souhaite combiner
Paramètre l : liste dont l'ont souhaite les combinaisons
Résultat : l'ensemble des k combinaisons de l
*)
let rec combinaison k l =
  match k,l with
  | 0, _ -> [[]]
  | _, [] -> []
  | _, t::q  ->
    let liste1 = combinaison k q in
    let liste2 = combinaison (k-1) q in
    liste1@( List.map (fun x -> t::x) liste2 )

(* TESTS *)
let%test _ = combinaison 0 [1;2;3;4] = [[]]
let%test _ = combinaison 1 [1;2;3;4] = [[4]; [3]; [2]; [1]]
let%test _ = combinaison 2 [1;2;3;4] = [[3; 4]; [2; 4]; [2; 3]; [1; 4]; [1; 3]; [1; 2]]
let%test _ = combinaison 3 [1;2;3;4] = [[2; 3; 4]; [1; 3; 4]; [1; 2; 4]; [1; 2; 3]] 
let%test _ = combinaison 4 [1;2;3;4] = [[1; 2; 3; 4]]