Re: [Caml-list] Cartesian product

[Erick Matsen <ematsen@gmail.com>]

Hello Ligia---


The following code takes cartesian products of lists:


let listListPrepend x ll = List.map (fun l -> x :: l) ll

let rec cartesianProduct = function
  | aList :: listList ->
      let prev = cartesianProduct listList in
      List.flatten (
	List.map (fun x -> listListPrepend x prev) aList)
  | [] -> [[]]


and could be easily adapted to the case of sets.


Erick


On Thu, Jul 30, 2009 at 11:53 AM, Peng Zang<peng.zang@gmail.com> wrote:
> -----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-----
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>