Re: [Caml-list] Cartesian product

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

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

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)

iD8DBQFKceqXfIRcEFL/JewRAnM5AKC3dnxh9uWl7kdRBKW68koS1f3dhACgxau4
ubBf3OXzaxkMeU3Cb848lJY=
=XZ4Q
-----END PGP SIGNATURE-----