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

["Nicolas Pouillard" <nicolas.pouillard@gmail.com>]

On 2/21/07, Erik de Castro Lopo <mle+ocaml@mega-nerd.com> wrote:
> Hi all,

Hi,

[...]

>
> Can anyone come up with a cleaner, more functional way of solving
> problems like this? I'm thinking that something like lazy lists
> might be a solution.
>

I need it some days ago and came to two different solutions.

In my case I needed to iterate over list permutations.

So in your case just use a function like range:

let range n =
 let rec aux i l =
     if i = 0 then l else i::(aux (i-1) l)
 in List.rev ( aux n [] )
;;

1/ The first is short but consume memory:

let fold = List.fold_right;;

let cartesian_product llz =
  fold begin fun ly llx ->
    fold begin fun y acc ->
      fold begin fun lx acc ->
        (y :: lx) :: acc
      end llx acc
    end ly []
  end llz [[]]
;;

cartesian_product [range p0; range p1; range p2];;

2/ This one consider list given as input like a counting base
(decimal, hexadecimal...).

type 'a enum = Stop | Elt of (('a list) * (unit -> 'a enum))

let enum_cartesian_product ll =
  let dupl l =
    List.rev_map begin fun x ->
      if x = [] then invalid_arg "enum_cartesian_product: empty list";
      (x, x)
    end l in
  let rec wrap_result res =
    let element = List.map (fun (x, _) -> List.hd x) res
    and kont () = increment (List.rev res) true []
    in (element, kont)
  and increment revll ret res =
    match revll with
    | [] ->
        if ret then (* it is the real end of the stream *) Stop
        else (* that's a element of stream *) Elt(wrap_result res)
    | (l, init) :: rest ->
        if ret then begin
          match l with
          | [] -> assert false
          | [ v ] -> increment rest true ((init, init) :: res)
          | v :: other -> increment rest false ((other, init) :: res)
        end else increment rest false ((l, init) :: res)
  in Elt(wrap_result (dupl ll))

let rec iter f =
  function
  | Elt(v, kont) -> f v; iter f (kont ())
  | Stop -> ()
;;

let e = enum_cartesian_product [range p0; range p1; range p2]
in
iter begin fun combi ->
  print_endline (String.concat "; " (List.map string_of_int combi))
end e;;

Hope that helps,

-- 
Nicolas Pouillard