folding over all combinations

combs.ml

(* a simple iterator, using the for loop, note that it counts objects starting from 1. *)
let iter_combs n k f =
  let rec gen v s j =
    if j > k then f v
    else for i = s to n do
        gen (i::v) (i+1) (j+1)
      done in
  gen [] 1 1


(* a production ready generalized fold, counting from 0  *)
let fold_combs n k f x =
  let rec gen v s j x =
    if j < k then loop s v j x
    else f v x
  and loop i v j x =
    if i < n
    then loop (i+1) v j (gen (i::v) (i+1) (j+1) x)
    else x in
  gen [] 0 0 x

(* a version without mutually recursive functions *)
let fold_combs n k f x =
  let rec loop i s c x =
    if i < n then
      loop (i+1) s c @@
      let c = i::c and s = s + 1 and i = i + 1 in
      if s < k then loop i s c x else f c x
    else x in
  loop 0 0 [] x

(* testing scaffolding *)
let pp_ints ppf xs =
  let pp_sep ppf () = Format.pp_print_string ppf ", " in
  Format.fprintf ppf "[%a]"
    Format.(pp_print_list ~pp_sep pp_print_int) xs

let print_combs n k =
  0 |> fold_combs n k @@ fun xs i ->
  Format.printf "%2d: %a@\n" i pp_ints xs;
  i + 1