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

[Pietro Abate <Pietro.Abate@anu.edu.au>]

On Wed, Feb 21, 2007 at 08:36:03PM +1100, Erik de Castro Lopo wrote:
> I'm currently working on something where I need to to generate a
> set of permutations that fit a set of rules. Currently I am doing
> something like:

I'm not sure this is exactly what you want... but I think it's a good
starting point to look at for this kind of problems. Making it lazy is
just a matter of changing the definition of the modules Seq.

module Seq =
    struct
        let mzero = []
        let return a = [a]
        let bind m f = List.flatten (List.map f m)
        let mplus = List.append
        let guard b = if b then return () else mzero
    end
        ;;

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

let test _ _ _ = true ;;

let find_comb p0 p1 =
    Seq.bind (range p0) (fun i0 ->
        Seq.bind (range p0) (fun i1 ->
            Seq.bind (range p1) (fun i2 ->
                Seq.bind (Seq.guard (test i0 i1 i2)) (fun _ ->
                    Seq.return (i0,i1,i2)
                )
            )
        )
    )
;;

# let a = find_comb 4 2 ;;
val a : (int * int * int) list =
  [(1, 1, 1); (1, 1, 2); (1, 2, 1); (1, 2, 2); (1, 3, 1); (1, 3, 2);
   (1, 4, 1); (1, 4, 2); (2, 1, 1); (2, 1, 2); (2, 2, 1); (2, 2, 2);
   (2, 3, 1); (2, 3, 2); (2, 4, 1); (2, 4, 2); (3, 1, 1); (3, 1, 2);
   (3, 2, 1); (3, 2, 2); (3, 3, 1); (3, 3, 2); (3, 4, 1); (3, 4, 2);
   (4, 1, 1); (4, 1, 2); (4, 2, 1); (4, 2, 2); (4, 3, 1); (4, 3, 2);
   (4, 4, 1); (4, 4, 2)]
#

pietro

-- 
++ Blog: http://blog.rsise.anu.edu.au/?q=pietro
++ 
++ "All great truths begin as blasphemies." -George Bernard Shaw
++ Please avoid sending me Word or PowerPoint attachments.
   See http://www.fsf.org/philosophy/no-word-attachments.html