Re: [Caml-list] Combinatorics in a functional way

["David Baelde" <david.baelde@gmail.com>]

Hi,

Here's a possibility. It certainly feels more functional, and also
consumes less memory, but I'm not sure that it fits your needs.
Basically the idea is to build an iterator over permutations, using a
function computing the next permutation from a given one -- this is
basically incrementing a list of digits seen as a number.

I'm lazy so I didn't pass min/max as parameters everywhere. My
solution doesn't use different upper bounds for digits like you (p0
for i0 to i2; p1 for i3 to i7) but it could be adapted.

let min = 2
let max = 4

exception Last

let rec init n = if n=0 then [] else min::(init (n-1))

let rec next acc = function
  | [] -> raise Last
  | x::l ->
      if x<max then List.rev_append acc ((x+1)::l) else next (min::acc) l

(* Iterates [f] over all lists of [len] digits between [min] and [max]. *)
let iter_combi len f =
  let rec iter cur =
    f cur ;
    iter (next [] cur)
  in
    try iter (init len) with Last -> ()

let _ =
  iter_combi 3
    (fun c ->
       print_string (String.concat " " (List.map string_of_int c)) ;
       print_newline ())

By the way, I started using this thing when coding in C to avoid the
memory cost of generating the list of permutations, not because it
felt more functional.

Hope that helps.
-- 
David