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 (10:36) From: David Baelde Subject: Re: [Caml-list] Combinatorics in a functional way
```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

```