benchmarking various implems of "combinations"

bench_combs.ml

(* ocamlfind opt -package sequence,benchmark -linkpkg truc.ml -o truc; ./truc*)

open Sequence.Infix

(* all the combinations *)
let rec combs = function
  | [] -> Sequence.return []
  | x :: tail ->
    Sequence.append (combs tail) (combs tail >|= fun l -> x :: l)

(* all the combinations *)
let rec combs2 = function
  | [] -> Sequence.return []
  | x :: tail ->
    combs2 tail >>=
    fun tail' -> Sequence.doubleton tail' (x::tail')

let seq_combs1 n l =
  combs l
  |> Sequence.filter (fun l->List.length l=n)
  |> Sequence.length

(* combinations of a given length *)
let combs3 k l =
  let n = List.length l in
  let rec aux k n l = match l with
    | [] when k=0 -> Sequence.return []
    | [] -> Sequence.empty
    | x :: tail ->
      let s1 =
        if n > k then (aux k (n-1) tail) else Sequence.empty
      and s2 =
        if n >= k
        then (aux (k-1) (n-1) tail >|= fun l->x::l)
        else Sequence.empty
      in
      Sequence.append s1 s2
  in
  aux k n l

let seq_combs2 k l =
  combs2 l
  |> Sequence.filter (fun l->List.length l=k)
  |> Sequence.length

let seq_combs3 k l =
  combs3 k l |> Sequence.length

let list_combs k l =
  let rec combinations l = match  l with
    | [] -> [[]]
    | h::q ->
      let qu = combinations q in
      List.rev_append (List.rev_map (fun y -> h::y) (qu)) qu 
  in
  combinations l
  |> List.filter (fun l-> List.length l = k)
  |> List.length

let test_fun f (k,n) =
  let l = Array.init n succ |> Array.to_list in
  f k l

let () =
  assert (list_combs 3 [1;2;3;4;5] = seq_combs2 3 [1;2;3;4;5]);
  assert (list_combs 3 [1;2;3;4;5] = seq_combs1 3 [1;2;3;4;5]);
  let module B = Benchmark in
  List.iter
    (fun (k,n) ->
       Printf.printf "\n\n*************\ntry with k=%d, n=%d\n" k n;
       Printf.printf "expected res: %d\n" (test_fun seq_combs1 (k,n));
       let res = 
         B.throughputN 3
           [ "seq_combs1", test_fun seq_combs1, (k,n);
             "seq_combs2", test_fun seq_combs2, (k,n);
             "seq_combs3", test_fun seq_combs3, (k,n);
             "list_combs", test_fun list_combs, (k,n);
           ]
       in
       B.tabulate res)
    [ (3,5);
      (3,15);
      (3,18);
      (10,20);
    ]