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

["Frédéric van der Plancke" <fvdp@decis.be>]

David Baelde wrote:
> 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 -> ()

You can also define iter_combi recursively in terms of itself:

(* Iterates [f] over all lists of [len] digits between [min] and [max]. *)
let rec iter_combi min max len f =
    assert (len >= 0);
    if len = 0 then (f [])
    else iter_combi min max (len - 1) (fun tail ->
        for x = min to max do
            f (x :: tail)
        done)

(if you want the lists be passed to f in lexicographical order, write f 
(List.rev (x::tail)) instead of f(x::tail).)

Frédéric
>
> 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.