Home     About     Download     Resources     Contact us

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

Browse thread
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:01) From: Pietro Abate Subject: Re: [Caml-list] Combinatorics in a functional way
```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

```