From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: ** X-Spam-Status: No, score=2.8 required=5.0 tests=DNS_FROM_RFC_POST,SPF_NEUTRAL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id 49628BBAF for ; Thu, 30 Jul 2009 22:08:30 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AmACAPeacUrRVdPKd2dsb2JhbACPJIowPwEMCwoHEKgBgR+QQQEDAgSEEwWBSQ X-IronPort-AV: E=Sophos;i="4.43,297,1246831200"; d="scan'208";a="33850180" Received: from mail-yw0-f202.google.com ([209.85.211.202]) by mail1-smtp-roc.national.inria.fr with ESMTP; 30 Jul 2009 22:08:21 +0200 Received: by ywh40 with SMTP id 40so1015357ywh.29 for ; Thu, 30 Jul 2009 13:08:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :date:message-id:subject:from:to:content-type :content-transfer-encoding; bh=4PCV3AGznRj8A3g3WdIENVdwnwDN/FdwNu3tpVaBGqw=; b=faYkCGj4qRADkOrpkoRTVSaeBE+3yKDZTGGT/Zo1J0A2lBQomp9mXweZ56LJ6d378i J3Gc01nGI+8RygAfQ+plwcIpSbTocMoGnApL9iOr+u8KKEAM7fi3E4u+59CrgeYMnZLu 7ycQTKZhwDL6Bo5Nn6rWltzJq1st+nRqnM2+M= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type:content-transfer-encoding; b=LVbi5zsvw/s66u8dtVOiEC7L2Zz1b2kA2Jz9Q5ov/4f1FSDaLPkzM82cDaGYRGSHHq 8VKq+YvrC8TsDJYGL7vyduPFpIB7SfHSOjgiJkU0Q3DZzCMSh3awaOma3Fk99MnrZux1 Z6FCCOHYS/0lXLoFIVUn4HXZaZC7zN9BxEn98= MIME-Version: 1.0 Received: by 10.100.6.17 with SMTP id 17mr1048903anf.73.1248984500942; Thu, 30 Jul 2009 13:08:20 -0700 (PDT) In-Reply-To: <200907301453.41250.peng.zang@gmail.com> References: <8401c38a0907301056x470687aah94b2b1295c6d1068@mail.gmail.com> <200907301446.47427.peng.zang@gmail.com> <200907301453.41250.peng.zang@gmail.com> Date: Thu, 30 Jul 2009 13:08:20 -0700 Message-ID: <243054520907301308r76c865e5v477fbea3aaa74af0@mail.gmail.com> Subject: Re: [Caml-list] Cartesian product From: Erick Matsen To: caml-list@inria.fr Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Spam: no; 0.00; alist:01 prev:01 flatten:01 prev:01 alist:01 hash:01 enum:01 enum:01 decr:01 decr:01 ocaml:01 beginner's:01 ocaml:01 bug:01 2009:98 Hello Ligia--- The following code takes cartesian products of lists: let listListPrepend x ll =3D List.map (fun l -> x :: l) ll let rec cartesianProduct =3D function | aList :: listList -> let prev =3D 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 wrote: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 > > I really should provide a bit more context. =A0It's a general implementat= ion for > crossing [Enum.t]s. =A0Eg. > > =A0let a =3D List.enum [1;2;3;4] > =A0let b =3D List.enum ['a'; 'b'; 'c'] > > =A0let c =3D 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. =A0But you can use this general implementation. =A0I= t >> assumes you have Enum (from Batteries, and ExtLib before). =A0The (~~) p= refix >> operator is "Obj.magic". >> >> >> Peng >> >> >> =A0 (* makes the cross product of the given array of enumerations *) >> =A0 let crossproductM enums initcount =3D >> =A0 =A0 let numenums =3D Array.length enums in >> =A0 =A0 let clean =3D Array.map clone enums in >> =A0 =A0 let initstate =3D enums in >> >> =A0 =A0 let rec cpmk cur curcount =3D >> =A0 =A0 =A0 let reseti i =3D cur.(i) <- clone clean.(i) in >> >> =A0 =A0 =A0 let tick () =3D >> =A0 =A0 =A0 =A0 let rec tick_aux place =3D >> =A0 =A0 =A0 =A0 =A0 if place >=3D numenums then () >> =A0 =A0 =A0 =A0 =A0 else >> =A0 =A0 =A0 =A0 =A0 =A0 let ple =3D cur.(place) in >> =A0 =A0 =A0 =A0 =A0 =A0 ignore (get ple); >> =A0 =A0 =A0 =A0 =A0 =A0 if is_empty ple then ( >> =A0 =A0 =A0 =A0 =A0 =A0 =A0 reseti place; >> =A0 =A0 =A0 =A0 =A0 =A0 =A0 tick_aux (place + 1) >> =A0 =A0 =A0 =A0 =A0 =A0 ) >> =A0 =A0 =A0 =A0 in tick_aux 0; decr curcount in >> >> =A0 =A0 =A0 let get () =3D Array.init numenums (fun i -> Option.get (pee= k cur.(i))) >> in >> >> =A0 =A0 =A0 let nx () =3D match !curcount with >> >> =A0 =A0 =A0 =A0 | 0 -> raise No_more_elements >> =A0 =A0 =A0 =A0 | 1 -> decr curcount; get () >> =A0 =A0 =A0 =A0 | x -> assert (x >=3D 0); let ans =3D get () in tick ();= ans in >> >> =A0 =A0 =A0 let ct () =3D !curcount in >> >> =A0 =A0 =A0 let cl () =3D cpmk (Array.init numenums (fun i -> clone cur.= (i))) >> (ref !curcount) in >> =A0 =A0 =A0 =A0 make nx ct cl >> =A0 =A0 in >> =A0 =A0 ( if initcount =3D=3D 0 then empty () >> =A0 =A0 =A0 else cpmk initstate (ref initcount) ) >> >> >> =A0 let crossproduct enums =3D >> =A0 =A0 let copy =3D Array.copy enums in >> =A0 =A0 let initcount =3D Array.fold_left (fun acc e -> count e * acc) 1= copy in >> =A0 =A0 crossproductM copy initcount >> >> >> =A0 let cross2 (t1:'a t) (t2:'b t) : ('a * 'b) t =3D >> =A0 =A0 ~~(crossproduct [|~~t1; ~~t2|]) >> >> =A0 let cross3 (t1:'a t) (t2:'b t) (t3:'c t) : ('a * 'b * 'c) t =3D >> =A0 =A0 ~~(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=3D > =3D8JeB > -----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 >