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.0 required=5.0 tests=AWL,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 mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id BB0C8BBAF for ; Thu, 30 Jul 2009 20:53:45 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AmgBALCIcUpKfVwakGdsb2JhbACZVD8BAQEBCQkMBxMDqD8KgRWQNgEDAgSEEwWBSYYL X-IronPort-AV: E=Sophos;i="4.43,296,1246831200"; d="scan'208";a="30607602" Received: from qw-out-2122.google.com ([74.125.92.26]) by mail2-smtp-roc.national.inria.fr with ESMTP; 30 Jul 2009 20:53:45 +0200 Received: by qw-out-2122.google.com with SMTP id 5so919156qwd.15 for ; Thu, 30 Jul 2009 11:53:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:from:reply-to:to:subject:date :user-agent:cc:references:in-reply-to:content-type :content-transfer-encoding:content-disposition:message-id; bh=Dy0P9atOdV+AyZehh6ZY40dSUCz4VGBE8/E3XqBRbKM=; b=tH7Ba53DEoI1900zb53v9lsFdr53Mq6cz2QzrhIabBLVqItJnI7FiVqmbdtGXO6x9X D7HiQ12tg9DGGw77kdZnpPJwn8q3h+e6p5YBTs5iSr8o6qpAhESxc+kb5RkMWQw7A2/f wN9IPZED47/SsviOQz1fATsizu+/gfvUFyLhE= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=from:reply-to:to:subject:date:user-agent:cc:references:in-reply-to :content-type:content-transfer-encoding:content-disposition :message-id; b=L3BHqYBuenlXVrlfRQOqlr/v65Kr1qSkpRjAjHcso+JZ4zRveCaQfTF9c9G1AzKQmQ 13FVHLOb7CT0Xwt9mbRrJ3DwJQoqWFm8hkpZdB+8z/MIAuyYZ8Y49GYbR/Eh2UdDD/WQ Qr/JPw4DwBZq6YuUswRfZPoD29nHIlTXNKwgo= Received: by 10.220.45.84 with SMTP id d20mr1857259vcf.90.1248980023925; Thu, 30 Jul 2009 11:53:43 -0700 (PDT) Received: from lawn-143-215-206-56.lawn.gatech.edu (lawn-143-215-206-56.lawn.gatech.edu [143.215.206.56]) by mx.google.com with ESMTPS id 20sm23233ywh.10.2009.07.30.11.53.42 (version=TLSv1/SSLv3 cipher=RC4-MD5); Thu, 30 Jul 2009 11:53:42 -0700 (PDT) From: Peng Zang Reply-To: peng.zang@gmail.com To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Cartesian product Date: Thu, 30 Jul 2009 14:53:37 -0400 User-Agent: KMail/1.9.9 Cc: Ligia Nistor References: <8401c38a0907301056x470687aah94b2b1295c6d1068@mail.gmail.com> <200907301446.47427.peng.zang@gmail.com> In-Reply-To: <200907301446.47427.peng.zang@gmail.com> Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200907301453.41250.peng.zang@gmail.com> X-Spam: no; 0.00; hash:01 enum:01 enum:01 decr:01 decr:01 ocaml:01 peng:98 peng:98 2009:98 2009:98 wrote:01 wrote:01 rec:01 rec:01 assert:01 -----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-----