Re: [Caml-list] Cartesian product

[Peng Zang <peng.zang@gmail.com>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I really should provide a bit more context.  It's a general implementation for 
crossing [Enum.t]s.  Eg.

  let a = List.enum [1;2;3;4]
  let b = List.enum ['a'; 'b'; 'c']

  let c = cross2 a b

yields [(1,'a'); (2,'a'); (3,'a'); (4,'a'); (1,'b'); ..]


There are implementations for converting Set to Enum in the same library(s) 
that provide Enum.

Peng

On Thursday 30 July 2009 02:46:41 pm Peng Zang wrote:
> Not that I know of.  But you can use this general implementation.  It
> assumes you have Enum (from Batteries, and ExtLib before).  The (~~) prefix
> operator is "Obj.magic".
>
>
> Peng
>
>
>   (* makes the cross product of the given array of enumerations *)
>   let crossproductM enums initcount =
>     let numenums = Array.length enums in
>     let clean = Array.map clone enums in
>     let initstate = enums in
>
>     let rec cpmk cur curcount =
>       let reseti i = cur.(i) <- clone clean.(i) in
>
>       let tick () =
>         let rec tick_aux place =
>           if place >= numenums then ()
>           else
>             let ple = cur.(place) in
>             ignore (get ple);
>             if is_empty ple then (
>               reseti place;
>               tick_aux (place + 1)
>             )
>         in tick_aux 0; decr curcount in
>
>       let get () = Array.init numenums (fun i -> Option.get (peek cur.(i)))
> in
>
>       let nx () = match !curcount with
>
>         | 0 -> raise No_more_elements
>         | 1 -> decr curcount; get ()
>         | x -> assert (x >= 0); let ans = get () in tick (); ans in
>
>       let ct () = !curcount in
>
>       let cl () = cpmk (Array.init numenums (fun i -> clone cur.(i)))
> (ref !curcount) in
>         make nx ct cl
>     in
>     ( if initcount == 0 then empty ()
>       else cpmk initstate (ref initcount) )
>
>
>   let crossproduct enums =
>     let copy = Array.copy enums in
>     let initcount = Array.fold_left (fun acc e -> count e * acc) 1 copy in
>     crossproductM copy initcount
>
>
>   let cross2 (t1:'a t) (t2:'b t) : ('a * 'b) t =
>     ~~(crossproduct [|~~t1; ~~t2|])
>
>   let cross3 (t1:'a t) (t2:'b t) (t3:'c t) : ('a * 'b * 'c) t =
>     ~~(crossproduct [|~~t1; ~~t2; ~~t3|])
>
> On Thursday 30 July 2009 01:56:50 pm Ligia Nistor wrote:
> > Hi,
> >
> > Is there an already implemented way of doing the Cartesian product of 2
> > sets in OCaml? My sets are of type Set.Make(Types), where Types is a
> > module I have defined.
> >
> > Thanks,
> >
> > Ligia
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.7 (GNU/Linux)

iD8DBQFKcew1fIRcEFL/JewRArLiAKCYGbfEHY5igi0IlM6f71tNAL2OqACeMUPR
qR8nC+F5QNRgaX19gSVtMsA=
=8JeB
-----END PGP SIGNATURE-----