This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Combinatorics in a functional way
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2007-02-21 (11:29) From: Nicolas Pouillard Subject: Re: [Caml-list] Combinatorics in a functional way
```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

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

```